Rabin Karp算法的一點修改版本的可行性

Question

我想要實現Rabin Karp算法的一點修改版本。我的想法是，如果我根據與每個字母相關的權重獲得給定模式的哈希值，那麼我不必擔心字符串，因此我只需拾取字符串的一部分，計算其哈希值並比較與模式的散列值不同，傳統的方法是計算字符串和模式的部分哈希值，然後檢查它們是否實際上相似或者它可能是一個字謎。這裏是我的代碼如下

string = "AABAACAADAABAABA" 
pattern = "AABA" 
#string = "gjdoopssdlksddsoopdfkjdfoops" 
#pattern = "oops" 

#get hash value of the pattern 
def gethashp(pattern): 
    sum = 0 
    #I mutiply each letter of the pattern with a weight 
    #So for eg CAT will be C*1 + A*2 + T*3 and the resulting 
    #value wil be unique for the letter CAT and won't match if the 
    #letters are rearranged 
    for i in range(len(pattern)): 
     sum = sum + ord(pattern[i]) * (i + 1) 
    return sum % 101 #some prime number 101 

def gethashst(string): 
    sum = 0 
    for i in range(len(string)): 
     sum = sum + ord(string[i]) * (i + 1) 
    return sum % 101 

hashp = gethashp(pattern) 
i = 0 
def checkMatch(string,pattern,hashp): 
    global i 
    #check if we actually get first four strings(comes handy when you 
    #are nearing the end of the string) 
    if len(string[:len(pattern)]) == len(pattern): 
     #assign the substring to string2 
     string2 = string[:len(pattern)] 
     #get the hash value of the substring 
     hashst = gethashst(string2) 
     #if both the hashvalue matches 
     if hashst == hashp: 
      #print the index of the first character of the match 
      print("Pattern found at {}".format(i)) 
     #delete the first character of the string 
     string = string[1:] 
     #increment the index 
     i += 1 #keep a count of the index 
     checkMatch(string,pattern,hashp) 
    else: 
     #if no match or end of string,return 
     return 

checkMatch(string,pattern,hashp) 

該代碼工作得很好。我的問題是這樣做的有效方式？是否有任何邏輯可能失敗的實例？我遇到過的所有Rabin Karp算法都不是用這個邏輯來代替每一場比賽，而是逐字逐個檢查，以確保它不是一個字謎。如果我這樣做是錯誤的？一旦哈希值匹配，我的意見就是使用這段代碼，你不必進一步檢查每個字符的字符串，你可以繼續下一步。

Answer 1

沒有必要只有anagrams與模式的散列值相沖突。任何其他具有相同散列值的字符串也可能發生衝突。相同的哈希值可以充當說謊者，因此需要逐字符匹配。

例如在你的情況下，你正在採取mod 100.採取任何不同的101模式，然後通過鴿子的原則，至少其中兩個將具有相同的散列。如果你使用其中一個作爲模式，那麼如果避免字符匹配，其他字符串的存在會錯誤輸出。而且，即使使用了你使用的散列，兩個字符也可以具有相同的散列值，這可以通過求解兩個線性方程來獲得。 例如，

DCE = 4*1 + 3*2 + 5*3 = 25 
CED = 3*1 + 5*2 + 4*3 = 25