Rabin-Karp 字符串哈希算法总结

Rabin-Karp 字符串哈希算法用到的场景分为两种：
第一种回文场景：正序hash值和逆序hash值的计算方法，相等时说明是回文

pre = (pre*base + endcode(s[i]))%mod   #顺序的前缀hash值
con = (endcode(s[i])*mul + con)%mod    #逆序的前缀hash值
1
2

第二种：判断字符串是否相等场景，不用一个个的对字符串进行计算，而是用hash唯一表示一个字符串

rem = pow(base,m-1,mod)
l = 0
for i in range(m-1):
    number1 = number1 *base + nums1[i]
for r in range(m-1,len(nums1)):
    number1 = (number1 *base + nums1[r])%mod
    number1 = (number1 - nums1[l]*rem)%mod
    l += 1
1
2
3
4
5
6
7
8