KMP算法

作者: 磨人的小表砸
来源: 51数据库
2021-07-28

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; const int maxm=1e6+10; char p[maxn]; char s[maxm]; int net[maxn]; int n,m; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n; cin>>p+1; cin>>m; cin>>s+1; for(int i=2,j=0;i<=n;i++){//预处理net数组  while(j&&p[j+1]^p[i]) j=net[j]; if(p[j+1]==p[i]) ++j; net[i]=j; } for(int i=1,j=0;i<=m;i++){ while(j&&p[j+1]^s[i]) j=net[j]; if(p[j+1]==s[i]) ++j; if(j==n){ cout<<i-n<<endl; j=net[j]; } } return 0; }

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; string s,p; int net[maxn]; int n,m; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); net[0]=-1; cin>>n; cin>>p; cin>>m; cin>>s; for(int i=1,j=-1;i<n;i++){ while(~j&&p[j+1]^p[i]) j=net[j]; if(p[j+1]==p[i]) ++j; net[i]=j; } for(int i=0,j=-1;i<m;i++){ while(~j&&p[j+1]^s[i]) j=net[j]; if(p[j+1]==s[i]) ++j; if(j==n-1){ cout<<i-n+1<<endl; j=net[j]; } } return 0; }