给定两个字符串a和b,找出a必须重复的最小次数,以便b是a的子字符串。如果没有这样的解决方案,返回-1。
例如,使用A=“abcd”和B=“cdabcdab”。
return 3,因为通过重复a三次(“abcdabcdabcd”),b是其子串;而b不是重复a两次(“abcdabcd”)的子串。
笔记
A和B的长度在1到10000之间。
解决方案有这样的解释:
现在,假设q是len(B)<=len(A*q)的最小数我们只需要检查B是a*q的子串还是a*(q+1)如果我们尝试k我不能把我的头绕在q+1的情况下,如果q是有b作为子串的最小数,那么在代码中我们为什么要检查q+1的情况。
问一个很久以前的人。
Repeated String Match
最佳答案
举个例子:a=“abcd”和b=“cdabcdab”。然后len(B) = 8
和len(A) = 4
因此,q = 2
但是A * 2 = abcdabcd
,所以B
不是子串因此,您还需要检查A * 3 = abcdabcdabcd
。
注意q
不是B
作为A*q
子串的最小数,而是len(B) <= len(A*q)
所包含的最小数。