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] 

，而這種解決方案可能很成功，我的主要目標是使用滾動散列實現多種模式搜索。你的想法將不勝感激。