There's this question on LeetCode (link):
Given two strings
A
andB
, find the minimum number of timesA
has to be repeated such thatB
is a substring of it. If no such solution exists, return-1
.For example, with
A = "abcd"
andB = "cdabcdab"
.Return
3
, because by repeatingA
three times (“abcdabcdabcd”
),B
is a substring of it; andB
is not a substring ofA
repeated two times ("abcdabcd"
).Note: The length of
A
andB
will be between1
and10000
.
The brute force solution provided on the website is this:
The question can be summarized as "What is the smallest
k
for whichB
is a substring ofA * k
?" We can simply try everyk
.Algorithm
Imagine we wrote
S = A+A+A+...
. IfB
is to be a substring ofS
, we only need to check whether someS[0:], S[1:], ..., S[len(A) - 1:]
starts withB
, asS
is long enough to containB
, andS
has period at mostlen(A)
.Now, suppose
q
is the least number for whichlen(B) <= len(A * q)
. We only need to check whether B is a substring ofA * q
orA * (q+1)
. If we tryk < q
, thenB
has larger length thanA * q
and therefore can't be a substring. Whenk = q+1
,A * k
is already big enough to try all positions forB
; namely,A[i:i+len(B)] == B
fori = 0, 1, ..., len(A) - 1
.
I understand this part:
If we try
k < q
, thenB
has larger length thanA * 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 forB
; namely,A[i:i+len(B)] == B
fori = 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.)?