AcWing 831. KMP字符串
原题链接
简单
作者:
comum
,
2023-09-19 01:09:49
,
所有人可见
,
阅读 37
字符串哈希做,可以过(18/19)个数据,但是 Segmentation Fault 为啥???
#include<iostream>
using namespace std;
const int N =200010,p=131;
typedef unsigned long long ull;
ull P[N],h[N],hp[N];
int get(int l,int r){
return h[r]-h[l-1]*P[r-l+1];
}
int getp(int l,int r){
return hp[r]-hp[l-1]*P[r-l+1];
}
int main(){
int n,m;
string strp,strs;
cin>>n>>strp>>m>>strs;
strp=" "+strp,strs=" "+strs;
ull ans=0;
P[0]=1;
for(int i=1;i<=m;i++){
P[i]=P[i-1]*p;
h[i]=h[i-1]*p+strs[i];
}
for(int i=1;i<=n;i++){
hp[i]=hp[i-1]*p+strp[i];
}
ans=getp(1,n);
for(int i=n;i<=m;i++){
if(ans==get(i-n+1,i)){
cout<<i-n<<" ";
}
}
return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
N不够大,得六次方
十分感谢,是我老眼昏花