当前位置： 移动技术网 > 移动技术>移动开发>IOS > KMP算法

KMP算法

2020年08月02日  | 移动技术网移动技术  | 我要评论

在这里插入图片描述 

#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; }

本文地址：https://blog.csdn.net/Charles6665/article/details/107711668

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网