哈希算法>>入门篇

两段字符串,判断它们是否相等,朴素解法是一个一个的判断,时间复制度较大。哈希算法把字符串转换成整数,这样时间复杂度从O(N)变成了O(1)。类似于二进制,用P进制将字符串装换成整数,为避免重复,一般认为P取131或者1331,使用unsigned long long 就可以,默认对结果模一个2^64,会有溢出的情况,但影响很小。(字符串默认都是小写字母,采用26进制) 例如 str=“abcd” Hash(str)= Hash数组存储字符串所有的前缀(憨憨小白不会打次方:p) 这里还可以用到简单的递归 Hash[i]=Hash[i-1]*P+s[i]-‘a’+1 对于字符串任意区间(L