时间戳

首页 > 解决方案 > 与 Boyer Moore 算法的重复字符串匹配关联

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

问题描述

在查看不同的博客/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。有人可以在这里帮助我吗？

提前致谢

标签： pythonalgorithmsearchdata-structuressubstring

解决方案

较小的字符串必须至少 m重复多次才能包含较大的字符串。

可以假设的最小值m是大于两个字符串的长度比（更大/更小）的最小整数，因为要包含 length 的子字符串l，字符串必须至少具有 length 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

推荐阅读