首页技术正文

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

工程师耀择技术 2022年11月14日

0 收藏 416 点赞 4,384 浏览 1084 个字

输入：

ABCDABTBD_TISABCDABC
ABCDABC

q为当前nxt处理的模版文本串下标；

k为“失配时去哪里”，详情请看注释。

————–我是求完nxt的分界线——————

q为当前文本串判断到哪里；

nxt为“失配时去哪里”。

输出：
nxt[q(1)]=k(0);
nxt[q(2)]=k(0);
nxt[q(3)]=k(0);
k(0)++;
nxt[q(4)]=k(1);
k(1)++;
nxt[q(5)]=k(2);
k(2)++;
nxt[q(6)]=k(3);
next数组求解完毕
q(0)++;
q(1)++;
q(2)++;
q(3)++;
q(4)++;
q(5)++;
q=nxt[q-1](0);
q=nxt[q-1](0);
q(0)++;
q(1)++;
q(2)++;
q(3)++;
q(4)++;
q(5)++;
q(6)++;
return i(19)-lp(7)+1;
pos=13

——————-我是代码分界线————————

 #include<iostream>
 #include<cstring>
 using namespace std;
 string T,P;
 int nxt[];
 void mkNxt(){
     nxt[]=;
     int k,q;
     for(k=,q=;q<P.length();q++){//遍历模版串以求出next数组
         while(k>&&P[k]!=P[q]){
             k=nxt[k-];//如果遇到“已经匹配过超过一个字符”又不匹配的地方，返回上一次求出的next，找到第二个已经匹配的地方
         }
         if(P[k]==P[q]){//如果成功就k++
             k++;//换句话说，k代表着当前能够匹配的最大长度
         }
         nxt[q]=k;//记录
     } }
 void KMP(){
     int q=;
     for(int i=;i<T.length();i++){//文本T和模版P匹配
         while(q>&&P[q]!=T[i]){//如果不匹配就拿出“最长前后缀表”
             q=nxt[q-];
         }
         if(P[q]==T[i]){//匹配一个就加大长度
             q++;
         }
         if(q==P.length()){
             cout<<i-q+<<endl;//完全匹配就输出
         }
     }
 }
 int main(){
     cin>>T>>P;
     mkNxt();
     KMP();
     for(int i=;i<P.length();i++){
         cout<<nxt[i]<<" ";
     }
 }