模式匹配KMP算法
关于KMP算法的原理网上有很详细的解释，我试着总结理解一下：
KMP算法是什么
以这张图片为例子
匹配到j=5时失效了，BF算法里我们会使i=1，j=0，再看s的第i位开始能不能匹配，而KMP算法接下来就去比较T[2]（next[5]=2）和S[5]
next数组什么意思？
就是当t[i]不匹配时,就让i=next[i]再去比较，则t[next[i]]前面的部分和s[j]前面一定是相同的，因为t[next[i]]前面的部分和t[i]前面的部分是相同的，图中相同颜色代表字符串相同部分。也就是我们利用模式串的自身匹配的特点，来减少和目标串的比较。
next数组怎么算？
我们算好next[i]，去算next[i+1]时分两种情况：
- T[i]==T[k] （k=next[i]） 时，next[i+1]=k+1。
- T[i]!=T[k] 时，先看图左，在匹配的部分里（灰色）有更小的一段（蓝色），是next[next[i]]前面的子串，根据next数组的含义，蓝色的和粉色的子串相同，因为两段灰色是相同的，那左蓝就和右粉相同，
- 如果这时Ti=Tnext[k]，那next[i+1]就是next[k]+1，否则继续找更小的一段，直到k=-1，那么next[i]=0。
void get_next(const string &T,int *next){
int i=0,k=-1;
next[i]=k;
while(T[i]){
if(k==-1||T[k]==T[i])
{
++k;
++i;
next[i]=k;
}else{
k=next[k];
}
}
}但是其实还可以再改进
上面算next[i+1]时不考虑T[i+1]是什么，T[i]失配，用T[next[i]]去比较，可以保证T[next[i]]前面的都能匹配，但是如果T[next[i]]==T[i]，跳到next[i]肯定还是失配，所以算next时要考虑一下T[next[i]]和T[i]是否相等。
算好next[i]，去算next[i+1]时：
如果 T[k]==T[i]且T[i+1]==T[k+1]，由于T[i+1]失配了，T[k+1]肯定也会失配，那next[i+1]应该继续跳到next[k+1]。
改进后的next计算代码：
void get_next()
{
int i=0,k=-1;
next[i]=k;
while(T[i])
{
if(k==-1||T[i]==T[k])
{
++k;
++i;
if(T[i] == T[k])
next[i] = next[k];
else
next[i] = k;
}
else
k=next[k];
}
}另一种get_next的写法
void get_next()
{
int i,k=-1;
next[0]=k;
for(i=1;T[i];i++){
while(k>=0 && T[k+1]!=T[i]) k=next[k];
if (T[k+1]==T[i]) k++;
next[i]=k;
}
}完整程序代码：
#include<iostream>
#include<cstring>
const int N = 1005;
int next[N];
char T[N],S[N];
void get_next()
{
int i=0,k=-1;
next[i]=k;
while(T[i]){
if(k==-1||T[i]==T[k]){
++i;
++k;
if(T[i]==T[k])
next[i]=next[k];
else
next[i]=k;
}else{
k=next[k];
}
}
}
int KMP()
{
int i=0,j=0;
while(S[j]&&(i==-1||T[i])){
if(i==-1||S[j]==T[i]){
++i;
++j;
}else{
i=next[i];
}
}
if(!T[i])return j-i;
return -1;
}
int main(){
std::cin>>T>>S;
get_next();
std::cout<<KMP()+1<<std::endl;
return 0;
}
/*
abcaccdacb
abcaccdaccccaccabcaccdaccacabcaccdacb
输出28
*/本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-12-03 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录