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

Question

在浏览了不同的博客/ SO问题后仍未找到答案来发布此问题我正在尝试围绕leetcode竞赛使用的解决方案/算法。这是问题：给定两个字符串A和B，找出必须重复的最小次数，以使B是它的子字符串。如果没有这样的解决方案，则返回-1。例如，使用A =“ abcd”和B =“ cdabcdab”。返回3，因为重复三遍A（“ abcdabcdabcd”），B是它的子字符串；并且B不是重复两次的A的子字符串（“ abcdabcd”）。我知道滚动哈希方法是首选方法，但我决定从博耶·摩尔方法开始。经过研究，我发现以下代码在幕后使用了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。特定算法可能取决于实现方式，但是由于流行且有效，因此很有可能成为波依摩尔或它的一种变体。