字符串哈希
2025-10-26 17:34:27
发布于：北京
18阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
int t;
ll k = 131, mod = 1 << 31;
char s1[1000005];
char s2[1000005];
ll a[1000005];//类似于 s1 的前缀哈希数组
ll p[1000005];//p[i] 是 k 的 i 次方 % mod
int main() {
p[0] = 1;
for (int i = 1; i <= 1e6; i++) {
p[i] = (p[i - 1] * k) % mod;
}
cin >> t;
while (t--) {
cin >> s1 + 1 >> s2 + 1;
ll num1 = 0, num2 = 0, cnt = 0;
ll l1 = strlen(s1 + 1);
ll l2 = strlen(s2 + 1);
//对 s2 进行哈希
for (int i = 1; i <= l2; i++) {
num2 = (num2 * k + (ll)(s2[i])) % mod;
}
//如何快速计算出 s1 中长度是 l2 的每一个子串的哈希值
// 143254568769879
// 1432、4325、3254....
// [l,r] = [1,r] - [1,l-1]*k^l2
for (int i = 1; i <= l1; i++) {
//[1,i] 的哈希值
a[i] = (a[i - 1] * k + (ll)(s1[i])) % mod;
if (i >= l2) {
//[i-l2+1,i]
num1 = (a[i] - a[i - l2] * p[l2]) % mod;
if (num1 == num2) {
cnt++;
}
}
}
cout << cnt << endl;
}
return 0;
}
全部评论 3
#include <bits/stdc++.h> using namespace std; typedef unsigned long long ll; ll k = 131, mod = 1 << 31; char s[1000005]; ll a[1000005]; ll p[1000005]; int main() { p[0] = 1; for (int i = 1; i <= 1e6; i++) { p[i] = (p[i - 1] * k) % mod; } while (cin >> s + 1) { if (s[1] == '.') break; int l = strlen(s + 1); for (int i = 1; i <= l; i++) { a[i] = (a[i - 1] * k + (ll)(s[i])) % mod; } for (int i = l; i >= 1; i--) { //个数 if (l % i == 0) { ll e = l / i;//长度 ll f = 1; //[1,e] [e+1,2*e] ,[2*e+1,3*e] for (int j = e + 1; j + e - 1 <= l; j += e) { //[1,e],[j,j+e-1] ll num = (a[j + e - 1] - a[j - 1] * p[e]) % mod; if (a[e] != num) { f = 0; break; } } if (f == 1) { cout << i << endl; break; } } } } return 0; }5天前 来自 北京
0
有帮助，赞一个