Repeated String Match: need help to understand the maximum number of repeats needed to be looked at There's this question on LeetCode (link):


  Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution exists, return -1.
  
  For example, with A = "abcd" and B = "cdabcdab".
  
  Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times ("abcdabcd").
  
  Note:
  The length of A and B will be between 1 and 10000.


The brute force solution provided on the website is this:


  The question can be summarized as "What is the smallest k for which B
  is a substring of A * k?" We can simply try every k.
  
  Algorithm
  
  Imagine we wrote S = A+A+A+.... If B is to be a substring of S, we
  only need to check whether some S[0:], S[1:], ..., S[len(A) - 1:]
  starts with B, as S is long enough to contain B, and S has period at 
  most len(A).
  
  Now, suppose q is the least number for which len(B) &lt;= len(A * q). We
  only need to check whether B is a substring of A * q or A * (q+1). If
  we try k &lt; q, then B has larger length than A * q and therefore can't
  be a substring. When k = q+1, A * k is already big enough to try all
  positions for B; namely, A[i:i+len(B)] == B for i = 0, 1, ..., len(A) - 1.


I understand this part:


  If we try k &lt; q, then B has larger length than A * q and therefore can't
  be a substring.


But I don't follow how the writer has arrived at this other conclusion:


  When k = q+1, A * k is already big enough to try all
  positions for B; namely, A[i:i+len(B)] == B for i = 0, 1, ..., len(A) - 1.


Why can we stop at k = q+1? Why is it not necessary to try q+2 (and q+3, etc.)?
Here is a proof by example. We want to check whether $B$ is a substring of some power of $A$. Instead, let us check whether $B$ is a substring of $A^\omega$, that is, $A$ repeated infinitely many times. It suffices to test the following starting positions (why?):

abcdabcdabcdabcd...
cdabcdab

abcdabcdabcdabcd...
 cdabcdab

abcdabcdabcdabcd...
  cdabcdab

abcdabcdabcdabcd...
   cdabcdab


In order to perform these checks, we don't need to consider $A^\omega$; it suffices to consider the smallest power of $A$ which covers the very last case. This power is $q+1$ (or possibly just $q$).