与 Boyer Moore 算法的重复字符串匹配关联

Question

在查看不同的博客/SO问题后发布此问题，但仍然找不到答案

我正在尝试围绕leetcode竞赛中使用的解决方案/算法进行思考。

问题是：

给定两个字符串 A 和 B，找到 A 必须重复的最小次数，使得 B 是它的子字符串。如果没有这样的解决方案，则返回 -1。

例如，A = "abcd" 和 B = "cdabcdab"。

返回 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。谁能在这里帮我？

提前致谢

Answer 1

较小的字符串必须至少重复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背后的算法似乎是cPython中的Boyer-Moore

。