# 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) <= 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.)?

• Please edit your question to include a link to the source of the copied material. – D.W. Apr 8 '19 at 15:39

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

• Is "proof by example" an acceptable way to prove correctness of algorithms? From Wikipedia: Proof by example (also known as inappropriate generalization) is a logical fallacy whereby one or more examples are claimed as "proof" for a more general statement.. Can you by any chance provide a general proof? – Neverflow Apr 9 '19 at 12:20
• Before you can prove something, you need to understand why it’s true. I hope I helped with that. Now you can provide a general proof. – Yuval Filmus Apr 9 '19 at 12:39