算法1
走错片场的字符串哈希
把模板串的哈希值求出来,然后O(n)遍历模式串,计算每个位置的哈希值即可
C++ 代码
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int NN = 1e5 + 17;
const int P = 131;
const unsigned long long mod = 0xffffffffffffffff;
char s1[NN * 10], s2[NN];
typedef unsigned long long ull;
ull h1[NN * 10], h2[NN], p[NN * 10];
int ans[NN * 10];
ull get(int l, int r){
return h1[r] - h1[l - 1] * p[r - l + 1] + mod + 1;
}
int main(){
int n, m;
cin >> n;
cin >> s2 + 1;
cin >> m;
cin >> s1 + 1;
p[0] = 1;
for(int i = 1; i <= max(n, m); ++i) p[i] = p[i - 1] * P;
for(int i = 1; i <= m; ++i) h1[i] = h1[i - 1] * P + s1[i];
for(int i = 1; i <= n; ++i) h2[i] = h2[i - 1] * P + s2[i];
if(n > m) return 0;
int ansk = 0;
ull nh = h2[n]; //模板串的哈希值
for(int i = 1; i <= m - n + 1; ++i){ //遍历模式串每个合法的“匹配起点”,计算哈希值是否匹配
if(get(i, i + n - 1) == nh)
ans[ansk++] = i - 1;
}
if(ansk) cout << ans[0];
for(int i = 1; i < ansk; ++i)
cout << ' ' << ans[i];
cout << endl;
return 0;
}