1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Please edit your question to include a link to the source of the copied material. $\endgroup$ – D.W. Apr 8 at 15:39
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Neverflow Apr 9 at 12:20
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Apr 9 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.