algorithm - Rabin Karp算法的部分修改版本的可行性

我正在尝试实现Rabin-Karp算法的一个稍微修改的版本我的想法是，如果我得到一个给定模式的散列值，根据与每个字母相关联的权重，那么我就不必担心anagrams，这样我就可以提取字符串的一部分，计算它的散列值，并与模式的散列值进行比较，这与传统的方法不同，传统的方法是同时计算字符串和模式的散列值然后检查它们是真的相似还是可能是一个字谜。下面是我的代码

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算法都没有对每个匹配项使用这个逻辑，而是进一步逐字符检查以确保它不是一个anagram如果我这样做是不对的吗我的意见是，只要哈希值匹配，就不必进一步逐个检查字符串，而只需转到下一个。

最佳答案

不必只有anagrams与模式的散列值冲突任何其他具有相同哈希值的字符串也可能发生冲突相同的散列值可以充当说谎者，因此需要逐字符匹配。
例如，在您的案例中，您使用的是mod 100取任何不同的101个模式，然后根据鸽子洞原理，其中至少有两个将具有相同的散列。如果将其中一个字符串用作模式，则如果避免字符匹配，则其他字符串的存在将错误输出。
此外，即使使用了哈希，两个anagram也可以具有相同的哈希值，可以通过求解两个线性方程来获得。
例如，

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