【斤斤计较的小Z——KMP / hash】

题目

KMP代码

#include <bits/stdc++.h>
using namespace std;const int N = 1e6+10;char s[N], p[N];
int nex[N];int main()
{cin >> p+1 >> s+1;int n = strlen(s+1);int m = strlen(p+1);//思路也是一致的，只要in > 0，就尝试拯救，最后补充一次匹配，如果不行就是0，如果行就是其它for(int i = 2, j = 0; i <= m; i++){while(j && p[j+1] != p[i]) j = nex[j];if(p[j+1] == p[i]) j++; //要么nex成功，要么j=0（此时也有可能匹配）nex[i] = j;}int cnt = 0;for(int i = 1, j = 0; i <= n; i++){while(j && p[j+1] != s[i]) j = nex[j];if(p[j+1] == s[i]) j++;if(j == m){j = 0;cnt++;}}cout << cnt;
}

hash代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;const int N = 1e6+10;
char s1[N], s2[N];const int base = 233;
const int mod = 1e9+7;ll f[N], qp[N];ll get_hash(int l, int r)
{ll ret = (f[r] - f[l-1] * qp[r-l+1] % mod + mod) % mod;return ret;
}
int main()
{cin >> s1+1 >> s2+1;int m = strlen(s1+1);int n = strlen(s2+1);qp[0] = 1;for(int i = 1; i <= n; i++){qp[i] = qp[i-1] * base % mod;f[i] = f[i-1] * base % mod + s2[i];f[i] %= mod;}ll hash1 = 0;for(int i = 1; i <= m; i++){hash1 = hash1 * base % mod + s1[i];hash1 %= mod;}int cnt = 0;for(int i = 1; i + m - 1 <= n; i++){int l = i, r = i+m-1;if(get_hash(l, r) == hash1) cnt++;}cout << cnt;
}