使用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.0m = math.ceil(m0)# m = 2但是，"cdabcdab"不在中"abcdabcd"。但是，如果我们再重复“ abcd” 1次，我们发现那"cdabcdab"是一个子字符串。进一步重复“ abcd”不会改变它是否可以作为子字符串找到。因此，仅需要检查遏制m和(m+1)重复。您共享的python代码不会实现任何搜索算法，而只会使用实现用于的任何搜索算法in。特定算法可能取决于实现方式，但是由于流行且有效，因此很有可能成为波依摩尔或它的一种变体。