在浏览了不同的博客后发布这个问题,但是仍然没有找到答案
我正试图用一个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/

10-12 12:29
查看更多