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

アナグラムだけがパターンのハッシュ値と衝突する必要はありません。同じハッシュ値を持つ他の文字列も衝突する可能性があります。同じハッシュ値が嘘つきの役目を果たすことができるので、文字ごとの一致が必要です。

たとえば、あなたの場合、100を取っています。別の101のパターンを取ってから、ピジョンホールの原則で、少なくとも2つが同じハッシュを持つでしょう。それらのパターンの1つをパターンとして使用すると、文字の一致を避けると、他の文字列の存在が出力を誤ることになります。

さらに、使用したハッシュを使用しても、2つのアナグラムは同じ2つの線形方程式を解くことによって得られる同じハッシュ値を持つことができます。例えば、

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