字符串hash Eowcoder 5026 E

發表於 2020-04-11 更新於 2024-04-11 分類於 NowCoder Disqus：文章字數： 371 所需閱讀時間 ≈ 1 分鐘

题

遇到了无数遍了

来讲一种常见的字符串hash吧

首先给一个字符串s，假设它只有小写英文字母

根据万物皆是数的想法

我们可以把它每一位通过 s[i]-'a'变成数字

这样原字符串就变成了一个数列，因为全是字母

所以可以26为进制 sum((s[i]-'a')*26^i)的形式把原来的数变成大的整数

如果两个字符串相等，那么这个大整数，相等，否则大整数不等。

通过取mod可以让它比较可以操作，和支持更长的长度

变成sum((s[i]-'a')*26^i) %p的形式

当我们有一个字符串s0s1...sn时

增删首尾都是可以通过考虑计算大整数的方式去处理，预处理26的幂次模p即可

这样长度为n的字符串的所有长度为m的连续子串的hash值，我们可以只用O(n)的时间就可完成

注意到上面的26是对于字母的情况，实际上,只要这个幂次的基大于每一位上的最大值即可，所以考虑单个字符的最大ascii

可以变成 sum(s[i] * b^i) %p 的形式， b 取质数重要吗迷? 然后p取尽量大的质数就行

$Hash(S) = \sum_{i=0->n-1} s[i] * b^i \mod p$