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

都与对应

为 '天'

在此先感谢您的帮助偏移。

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] 

，而这种解决方案可能很成功，我的主要目标是使用滚动散列实现多种模式搜索。你的想法将不胜感激。