#程序员福大大#2023-11-08:用go语言,字符串哈希原理和实现
比如p = 233, 也就是课上说的选择的质数进制
" 3 1 2 5 6 ..."
0 1 2 3 4
hash[0] = 3 * p的0次方
hash[1] = 3 * p的1次方 + 1 * p的0次方
hash[2] = 3 * p的2次方 + 1 * p的1次方 + 2 * p的0次方
hash[3] = 3 * p的3次方 + 1 * p的2次方 + 2 * p的1次方 + 5 * p的0次方
hash[4] = 3 * p的4次方 + 1 * p的3次方 + 2 * p的2次方 + 5 * p的1次方 + 6 * p的0次方
次方是倒过来的,课上讲错了
所以hash[i] = hash[i-1] * p + arr[i],这个方式就可以得到上面说的意思
于是,你想得到子串"56"的哈希值
子串"56"的哈希值 = hash[4] - hash[2]*p的2次方(就是子串"56"的长度次方)
hash[4] = 3 * p的4次方 + 1 * p的3次方 + 2 * p的2次方 + 5 * p的1次方 + 6 * p的0次方
hash[2] = 3 * p的2次方 + 1 * p的1次方 + 2 * p的0次方
hash[2] * p的2次方 = 3 * p的4次方 + 1 * p的3次方 + 2 * p的2次方
所以hash[4] - hash[2] * p的2次方 = 5 * p的1次方 + 6 * p的0次方
这样就得到子串"56"的哈希值了
抱歉,课上讲错了。应该是上面的方式。
所以,子串s[l...r]的哈希值 = hash[r] - hash[l-1] * p的(r-l+1)次方
也就是说,hash[l-1] * p的(r-l+1)次方,正好和hash[r]所代表的信息,前面对齐了
减完之后,正好就是子串s[l...r]的哈希值。