AcWing 831. 学kmp的意义在哪
原题链接
简单
作者:
acjiangly
,
2024-04-12 22:00:54
,
所有人可见
,
阅读 9
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N=1e5+10,P=131;
string s,p;
int n,m;
ull hp[N],hs[N*10],pp[N*10],t;
ull get(int i,int j)
{
return hs[j]-hs[i-1]*pp[j-i+1];
}
int main()
{
cin>>n>>p>>m>>s;
p="#"+p;
s="#"+s;
pp[0]=1;
for(int i=1;i<=n;i++)//处理长度为n的模板p串
{
hp[i]=hp[i-1]*P+p[i];
pp[i]=pp[i-1]*P;
}
for(int i=1;i<=m;i++)//处理长度为m模板s串
{
hs[i]=hs[i-1]*P+s[i];
pp[i]=pp[i-1]*P;
}
t=hp[n];//p串的哈希值
for(int i=1,j=n;j<=m;i++,j++)//枚举长度为m的s串
{
if(get(i,j)==t) cout<<i-1<<' ';
}
}