python - 没有散​​列的 Karp-Rabin 多模式搜索

Question

我在使用 Karp-Rabin（没有散列）进行多模式搜索时遇到问题。这是我的例子：

_string="today is a good day"

_patterns=['good', 'day']

def multiple_pattern_search(string,substrings,size):
    stringsize=string[:size]
    for i in range(len(stringsize)-size+1):
        if stringsize in substrings and string[:i+size-1] in substrings:
            return i
        stringsize=string[1:size+1]
    return 

print(multiple_pattern_search(_string,_sublist,3))

输出：None

预期输出：2,16

两者都对应于“day”的偏移量

在此先感谢您的帮助。

PS。是否有任何带有散列的 Karp-Rabin 多模式搜索的 python 实现？

Answer 1

解决方案

def multiple_pattern_search(string,substrings,size):
        matched=[]
        #stringsize=string[:size]
        for i in range(len(string)-size+1):
            stringsize=string[i:size+i]
            if stringsize not in substrings:
                substring=string[i:size+i]
            if stringsize in substrings:
                if string[i:size+i] in substrings:
                    matched.append(i)
        return matched

    print(multiple_pattern_search(_string,_patterns,3))

    Output: [2, 16]

虽然这个解决方案可能有效，但我的主要目标是使用滚动哈希实现多模式搜索。您的想法将不胜感激。