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$
1
  • $\begingroup$ Please edit your question to include a link to the source of the copied material. $\endgroup$
    – D.W.
    Apr 8, 2019 at 15:39

1 Answer 1

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$
2
  • $\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, 2019 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$ Apr 9, 2019 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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