详解:https://www.cnblogs.com/yjiyjige/p/3263858.html
https://blog.csdn.net/lee18254290736/article/details/77278769
字符串匹配的暴力方法与KMP的比较:
遇到以下情况时:
-
暴力方法把匹配的指针下移一位
-
KMP根据next数组跳过不需要遍历的部分:
KMP的思想:
利用已经部分匹配这个有效信息,保持i指针不回溯,通过修改j指针,让模式串尽量地移动到有效的位置。
推理:
当T[i] != P[j]时
有T[i-j ~ i-1] == P[0 ~ j-1]
由P[0 ~ k-1] == P[j-k ~ j-1]
必然:T[i-k ~ i-1] == P[0 ~ k-1]
PS:为什么是i-k~i-1而不是i-k~i-x(x>1)?
因为如果是i-k~i-x的话说明就算j移到i-k还是无法匹配i-x~i-1这段字符串,所以必须以i-k开头i-1结尾。
next数组的含义:(next数组由匹配串ABCE自己生成)
当j位失配时,j需要回退到的地方,即next[j]。(j是pattern对应的指针)
next数组如何定义?又如何判断要跳过多少元素呢?
Next[0]==Next[1]== -1是默认值,但是在处理中第一位pattern[0]不匹配时要i++,其他只需要j=0即可。如果pattern[i]不匹配,则将j指针指向Next[i]=2,即j=Next[];
Next数组的写法:
// 当第n位不匹配时怎么跳。
void getnext(char pattern[]){
int i=0,j=0,k=0;
// 事先约定好的两位
Next[0]=-1;
// 第一位不跳,-1位不存在匹配的情况。
Next[1]=-1;
// 第二位不匹配,但第一位匹配,移动一位。比如ab与ac不匹配,肯定将i移动到b后面。
for(i=2;i<strlen(pattern);i++){
// 从pattern[2]开始不匹配时
Next[i]=-1;
for(j=i-2;j>=0;j--){
// j的结束位置从[0,i-2],开始位置默认0的贴前字符串
for(k=0;k<=j;k++){
// [0,i-2]的贴后字符串
//cout<<"i:"<<i<<" k:"<<k<<" "<<pattern[k]<<" j:"<<j<<" "<<pattern[i-1-j+k]<<endl;
if(pattern[k]==pattern[i-1-j+k]){
}
else{
break;
}
}
if(k==j+1){
Next[i]=j+1;
// 最长的匹配子串长度(0-j),所以长度是j+1
break;
}
}
}
}
在k的循环体里面:
Next数组基础上的kmp:
void kmp(char text[],char pattern[]){
int i=0,j=0;
int t=strlen(text);
int p=strlen(pattern);
bool pass=false;
while(i<t){
// 只要看text的指针有没有越界即可,反正pattern的指针j越界就会跳出循环匹配成功
//cout<<i<<" "<<j<<" "<<Next[j]<<endl;
if(text[i]==pattern[j]){
i++;
j++;
}
else{
if(Next[j]==-1&&j==0){
// 如果没有找到串内重复的串,只需要将pattern的指针指向开头就好。
// ab与ac如果把j=0,会陷入死循环。
i++;
}
else if(Next[j]==-1){
j=0;
}
else{
// 如果匹配失败,将j指针指向Next[j]对应的地址。
j=(Next[j]);
}
}
if(j==strlen(pattern)){
pass=true;
cout<<"\nmatch: ["<<i-strlen(pattern)<<","<<i-1<<"]"<<endl;
show(text,i-strlen(pattern),i-1);
}
}
if(!pass)cout<<"\nNo matching"<<endl;
}