LOJ 103子串查找——用hash代替kmp算法
题意
给出两个字符串 $s_1,s_2$，求 $s_2$ 在 $s_1$ 中出现的次数。
分析
预处理出两个字符串的哈希值，再逐位比较。
时间复杂度为 $O(n+m)$，和 $kmp$ 算法一样。
可能常数大一点点，还有就是没法用 $kmp$ 的 $next$ 数组。
#include <bits/stdc++.h> using namespace std; typedef unsigned long long ull; const ull base = 233; const int maxn = 1e6 + 10; ull h[maxn], p[maxn], ha; char s1[maxn], s2[maxn]; int main() { scanf("%s%s", s1+1, s2+1); int n = strlen(s1+1), m = strlen(s2+1); for(int i = 1;i <= m;i++) ha = ha * base + (ull)s2[i]; p[0]=1; for(int i = 1;i <= n;i++) { h[i] = h[i-1]*base + (ull)s1[i]; p[i] = p[i-1] * base; } int l=1, r = m, ans = 0; while(r <= n) { if(h[r] - h[l-1]*p[m] == ha) ans++; l++, r++; } printf("%d ", ans); return 0; }