【字符串处理】关于KMP算法输出的是什么&代码

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 string T,P;
 5 int nxt[1000002];
 6 void mkNxt(){
 7     nxt[0]=0;
 8     int k,q;
 9     for(k=0,q=1;q<P.length();q++){//遍历模版串以求出next数组
10         while(k>0&&P[k]!=P[q]){
11             k=nxt[k-1];//如果遇到“已经匹配过超过一个字符”又不匹配的地方，返回上一次求出的next，找到第二个已经匹配的地方
12         }
13         if(P[k]==P[q]){//如果成功就k++
14             k++;//换句话说，k代表着当前能够匹配的最大长度
15         }
16         nxt[q]=k;//记录
17     }
18     
19 }
20 void KMP(){
21     int q=0;
22     for(int i=0;i<T.length();i++){//文本T和模版P匹配
23         while(q>0&&P[q]!=T[i]){//如果不匹配就拿出“最长前后缀表”
24             q=nxt[q-1];
25         }
26         if(P[q]==T[i]){//匹配一个就加大长度
27             q++;
28         }
29         if(q==P.length()){
30             cout<<i-q+2<<endl;//完全匹配就输出
31         }
32     }
33 }
34 int main(){
35     cin>>T>>P;
36     mkNxt();
37     KMP();
38     for(int i=0;i<P.length();i++){
39         cout<<nxt[i]<<" ";
40     }
41 }