ACM|字符串哈希（HDU1686字符串匹配hash和kmp对比，POJ3974最长回文子串hash和manacher对比） hash|数据结构|#

字符串哈希 Hash 的思想 Hash 的核心思想在于，将输入映射到一个值域较小、可以方便比较的范围。

W a r n i n g ！ Warning！ Warning！
这里说的“值域较小”在不同的情况下意义是不一样的：
在哈希表中：值域需要小到能够接受线性的空间和时间。
而在字符串哈希中，值域需要小到能够快速比较( 1 0 9 ? 1 0 18 10^9 \, 10^{18} 1091018都可以快速比较)。
同时，为了降低哈希冲突率，值域也不能太小。

我们定义一个把字符串映射到整数的函数 h a s h hash hash，这个就是 h a s h hash hash函数，可以很方便的来帮助我们判断两个字符串是否相等，我们希望哈希函数在值不一样的时候，两个字符串一定不同。

另外，反过来不需要成立，oi-wiki把这种条件称为单侧错误。

在字符串 h a s h 字符串hash 字符串hash里面我们最应该关注的是，时间复杂度和 h a s h hash hash的准确率。
一般我们的 h a s h hash hash函数都是多项式的： h a s h ( s ) = ∑ s [ i ] × b i ( ? m o d ? M ) hash(s)=\sum s[i] \times b^{i} \quad(\bmod M) hash(s)=∑s[i]×bi(modM)
这里面的b b b和 M M M需要选取得足够合适才行，以使得h a s h hash hash 函数的值在 [ 0 , M ) [0,M) [0,M)分布尽量均匀。
如果 b b b和M M M互质，在输入随机的情况下，这个 h a s h hash hash 函数在 [ 0 , M ) [0,M) [0,M)上每个值概率相等，此时单次比较的错误率为 1 M \frac{1}{M} M1? 。所以，哈希的模数一般会选用大质数。
代码实现未优化版：

#include using namespace std; const int M = 1e9 + 7; const int B = 233; typedef long long ll; int gethash(const string &s) { int ans = 0, siz = s.size(); for (int i = 0; i < siz; ++i) { ans = (ll)(ans * B + s[i]) % M; } return ans; } bool cmp(const string &s, const string &t) { return hash(s) == hash(t); }

hash 的分析与改进错误率:若进行 n n n次比较，每次错误率为 1 M \frac{1}{M} M1? ，那么总错误率是 1 ? ( 1 ? 1 M ) n 1-(1-\frac{1}{M})^n 1?(1?M1?)n 。在随机数据下，若 M = 1 0 9 + 7 M=10^9+7 M=109+7 , n = 1 0 6 n=10^6 n=106 ，错误率约为 1 1000 \frac{1}{1000} 10001? ，并不足够小，不能忽略。
所以，进行字符串哈希时，经常会对两个大质数分别取模，这样的话哈希函数的值域就能扩大到两者之积，错误率就非常小了。
关于多次询问子串哈希单次计算一个字符串的哈希值复杂度是 O ( n ) O(n) O(n) ，其中n n n为串长，与暴力匹配没有区别，如果需要多次询问一个字符串的子串的哈希值，每次重新计算效率非常低下。
一般采取的方法是对整个字符串先预处理出每个前缀的哈希值，将哈希值看成一个 b b b进制的数对 M M M取模的结果，这样的话每次就能快速求出子串的哈希了：

令 h a s h i ( s ) hash_i(s) hashi?(s)表示 h a s h ( s [ 1... i ] ) hash(s[1...i]) hash(s[1...i])，那么 h a s h ( s [ l . . . r ] ) = h a s h r ( s ) ? h a s h l ? 1 ( s ) b l ? 1 hash(s[l...r])=\frac{hash_r(s)-hash_{l-1}(s)}{b^{l-1}} hash(s[l...r])=bl?1hashr?(s)?hashl?1?(s)?，其中 1 b l ? 1 \frac{1}{b^{l-1}} bl?11?也可以预处理出来，用乘法逆元或者是在直接比较哈希值的时候等式两边同时乘上 b b b的若干次化为整式都可。

这样的话，就可以在 O ( n ) O(n) O(n)的时间复杂度内预处理后达到 O ( 1 ) O(1) O(1)的计算子串哈希值。
代码实现

#include using namespace std; const int B = 233; typedef long long ll; ll h[1000005], p[1000005]; void init(string s) { p[0] = 1; h[0] = 0; int len = s.length(); for (int i = 1; i <= len; ++i) { p[i] = p[i - 1] * B; h[i] = h[i - 1] * B + s[i - 1]; } }ll gethash(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; }

字符串hash的应用字符串匹配求出模式串的哈希值后，求出文本串每个长度为模式串长度的子串的哈希值，分别与模式串的哈希值比较即可。
预处理复杂度为 O ( n ) O(n) O(n)，查询为 O ( 1 ) O(1) O(1)，然后 O ( m ) O(m) O(m)遍历子串比较哈希值，总复杂度 O ( n ) O(n) O(n)和kmp的复杂度一样。
HDU1686，求模式串在文本串中出现的次数。
h a s h hash hash

ACM|字符串哈希（HDU1686字符串匹配hash和kmp对比，POJ3974最长回文子串hash和manacher对比）

文章图片

#include #include using namespace std; const int N = 1e6 + 5; const int B = 233; typedef long long ll; ll h[N], p[N]; void init(string s) { p[0] = 1; h[0] = 0; int len = s.length(); for (int i = 1; i <= len; ++i) { p[i] = p[i - 1] * B; h[i] = h[i - 1] * B + s[i - 1]; } }ll gethash(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; } int main() { ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; while (t--) { string a, b; cin >> a >> b; init(a); int ans = 0, lena = a.length(), lenb = b.length(); ll hasha = gethash(1, lena); init(b); for (int i = lenb - lena + 1; i; --i) { if (hasha == gethash(i, i + lena - 1)) { ans++; } } cout << ans << endl; } return 0; }

k m p kmp kmp

文章图片

#include using namespace std; const int N = 1e6 + 10; const int M = 1e6 + 10; int n, m; int ne[N]; char s[M], p[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; while (t--) { cin >> p + 1 >> s + 1; int ans = 0, n = strlen(p + 1), m = strlen(s + 1); for (int i = 2, j = 0; i <= n; i++) { while (j && p[i] != p[j + 1]) { j = ne[j]; } if (p[i] == p[j + 1]) { j++; } ne[i] = j; }for (int i = 1, j = 0; i <= m; i++) { while (j && s[i] != p[j + 1]) { j = ne[j]; } if (s[i] == p[j + 1]) { j++; } if (j == n) { { ans++; j = ne[j]; } } } cout << ans << endl; } return 0; }

最长回文子串首先需要分别预处理正着和倒着的哈希值，然后，二分答案，判断是否可行时枚举回文中心（对称轴），哈希判断两侧是否相等。
POJ3974，求最长回文子串的长度。
h a s h hash hash时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn):

文章图片

#include #include #include using namespace std; const int N = 1e6 + 5; const int bas = 13331; typedef long long ll; int hashl[N << 1], hashr[N << 1], p[N << 1]; char s[N << 1]; ll gethash(int hash[], int l, int r) { return hash[r] - hash[l - 1] * p[r - l + 1]; } int main() { int t = 1; p[0] = 1; for (int i = 1; i < 2 * N; i++) { p[i] = p[i - 1] * bas; } while (~scanf("%s", s + 1)) { if (strcmp(s + 1, "END") == 0) { break; } int n = strlen(s + 1); for (int i = n * 2; i > 0; i -= 2) { s[i] = s[i / 2]; s[i - 1] = 'z' + 1; } n *= 2; for (int i = 1, j = n; i <= n; i++, j--) { hashl[i] = hashl[i - 1] * bas + s[i] - 'a' + 1; hashr[i] = hashr[i - 1] * bas + s[j] - 'a' + 1; }int ans = 0; for (int i = 1; i <= n; i++) { int l = 0, r = min(i - 1, n - i); while (l < r) { int mid = (l + r + 1) >> 1; if (gethash(hashl, i - mid, i - 1) != gethash(hashr, n - (i + mid) + 1, n - (i + 1) + 1)) { r = mid - 1; } else { l = mid; } } if (s[i - l] == 'z' + 1) { ans = max(ans, l); } else { ans = max(ans, l + 1); } } printf("Case %d: %d\n", t++, ans); }return 0; }

【ACM|字符串哈希（HDU1686字符串匹配hash和kmp对比，POJ3974最长回文子串hash和manacher对比）】manacher的时间复杂度 O ( n ) O(n) O(n):

文章图片

#include #include #include using namespace std; const int N = 1e6 + 10; char s1[N * 2], s2[N * 2]; // 开双倍数组 int p[N * 2], n; // p数组记录每点的回文长度， n记录数组长度int manacher() { int mx = 0, id, ans = 0; for (int i = 1; i < n; ++i) { if (mx > i) { p[i] = min(p[2 * id - i], mx - i); } else { p[i] = 1; } while (s2[i + p[i]] == s2[i - p[i]]) { ++p[i]; } if (p[i] + i > mx) { mx = p[i] + i, id = i; } if (p[i] > ans) { ans = p[i]; } } return ans; }void init() { // 使字符长度变为两倍 s2[0] = s2[1] = '#'; for (int i = 0; i < n; ++i) { s2[(i << 1) + 2] = s1[i], s2[(i << 1) + 3] = '#'; } n = (n << 1) + 2; s2[n] = '?'; }int main() { int t = 1; while (~scanf("%s", s1)) { if (strcmp(s1, "END") == 0) { break; } n = strlen(s1); init(); printf("Case %d: %d\n", t++, manacher() - 1); } return 0; }