基础算法--KMP匹配字符串

 1 #include<iostream>
 2 using namespace std;
 3 int n,m;
 4 const int N=1e5+10;
 5 const int M=1e6+10;
 6 char p[N],s[M];//p是模板串，s是源串
 7 int ne[N];//ne表示前缀和后缀匹配的最长长度
 8 int main(void){
 9     //j表示的都是下一个将要匹配的字符是j+1
10     cin>>n>>p+1>>m>>s+1;
11     for(int i=2,j=0;i<=n;i++){
12         while(j&&p[i]!=p[j+1]) j=ne[j];
13         if(p[i]==p[j+1]) j++;
14         ne[i]=j;
15     }
16     for(int i=1,j=0;i<=m;i++){
17         while(j&&s[i]!=p[j+1]) j=ne[j];
18         if(s[i]==p[j+1]) j++;
19         if(j==n){
20             cout<<i-n+1 -1<<" ";//-1的原因的题目要求从0开始，而我们是从1开始的
21             j=ne[j];
22         }
23     }
24     return 0;
25 }