在浏览了不同的博客后发布这个问题,但是仍然没有找到答案
我正试图用一个leetcode竞赛中使用的解决方案/算法来解决问题。
问题是:
给定两个字符串a和b,找出a必须重复的最小次数,以便b是a的子字符串。如果没有这样的解决方案,返回-1。
例如,使用A=“abcd”和B=“cdabcdab”
Return 3,因为通过重复A三次(“abcdabcdabcd”),B是其子串;而B不是重复A两次(“abcdabcd”)的子串。
我知道滚动散列方法是首选的方法,但我决定从boyer-moore方法开始。
在做了一些研究之后,我了解到下面的代码在幕后使用了boyer-moore算法。代码如下:
def repeatedStringMatch(self, A, B):
"""
:type A: str
:type B: str
:rtype: int
"""
m = math.ceil(len(B)/len(A))
if B in A * m:
return m
elif B in A * (m + 1):
return m + 1
else:
return -1
基于我对算法的理解,我不确定上面的解决方案是如何使用BM方法的。
我不清楚这句台词是什么
m = math.ceil(len(B)/len(A))
是的,为什么我们要用这种方式找到M。有人能帮我吗?
提前谢谢
最佳答案
较小的字符串必须重复至少m
次才能包含较大的字符串。m
可以假定的最小值是大于两个字符串长度之比(较大/较小)的最小整数,因为要包含长度l
的子字符串,字符串必须至少具有长度l
。
使用您共享的示例。
A = "abcd"
B = "cdabcdab"
m0 = len(B) / len(A)
# m0 == 2.0
m = math.ceil(m0)
# m = 2
但是,
"cdabcdab"
不包含在"abcdabcd"
中。但是,如果我们再重复“abcd”1次,就会发现"cdabcdab"
是一个子串。进一步重复“abcd”不会改变它是否可以作为子字符串找到因此,只需检查容器中是否有m
和(m+1)
重复。您共享的python代码没有实现任何搜索算法,它只是使用实现用于
in
的任何搜索算法具体的算法可能依赖于实现,但是它很可能是boyer-moore或的变体,因为它是流行和有效的。编辑:
B in A
背后的算法似乎是boyer-moore in cpython关于python - 使用Boyer Moore算法的重复字符串匹配关联,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/51237938/