Repeated String Match: need help to understand the maximum number of repeats needed to be looked at

Question

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) <= len(A * q). We only need to check whether B is a substring of A * q or A * (q+1). If we try k < 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 < 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.)?

Answer 1

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$).