文章目录[x]
- 1:KMP算法
- 1.1:算法步骤
KMP算法
KMP算法是一种模式匹配算法,可以尽量减少主串与模式串的匹配次数
算法步骤
1.生成next数组(前缀表)
例如字符串:ABADCABD
AB | 0 |
---|---|
ABA | 1 |
ABAD | 0 |
ABADC | 0 |
ABADCA | 1 |
ABADCAB | 2 |
所以生成前缀表数组为[0,0,1,0,0,1,2]
原因:
例如AB,前缀和后缀分别为A和B,并部相同,所以最长公共前后缀为0;例如ABA,前缀和后缀分别为,A,AB,后缀:A,BA,所以最长的公共前后缀长度为1;....
例如ABADCAB,最长公共前后缀为AB,长度为2
代码实现:
using namespace std;
void prefix(char res[],int tmp[],int l){
tmp[0]=0;
int len=0; //初始化最长公共后缀长度
int i=1; //初始化后缀位置
while(i<l){
if(res[i]==res[len]){
len++;
tmp[i]=len;
i++;
}else{
if(len>0)
len=tmp[len-1];
else{
tmp[i]=len;
i++;
}
}
}
}
int main(){
char *s="ABDABD";
int ans[6];
prefix(s,ans,6);
for(int i=0;i<6;i++){
cout<<ans[i]<<endl;
}
return 0;
}
而next数组则是把整个前缀表向后移动一位,并把第一位置为-1,表示,当第一个都不满足的时候,子串和主串均向后移动一位进行比较
2.kmp算法过程
next数组作用:
子串:A B A D C A B D next数组为:[-1,0,0,1,0,0,1,2]
例如,当主串与子串第八个不相同时候,那么按照暴力方法,子串和主串都将回溯到第二个进行重新比较,而有了next数组,则可以利用数组对照第八个元素值为2,那么只需要j回溯到子串第二个元素,并将该元素与当前不相同的位置对其即可继续进行比较。
如果连续匹配失败的话,那么就将最长公共前缀数组前移一位,相当于最长公共前缀长度-1,并跳转到相应的元素再进行比对,直至达到第一个数组时候,值为-1,那么就整体子串和主串均向后移动一位
KMP完整算法
using namespace std;
void prefix(char res[],int tmp[],int l){
tmp[0]=-1;
int len=0; //初始化最长公共后缀长度
int i=1; //初始化后缀位置
while(i<l){
if(res[i]==res[len]){
len++;
tmp[i]=len;
i++;
}else{
if(len>0)
len=tmp[len-1];
else{
tmp[i]=len;
i++;
}
}
}
}
void kmp(char s1[],char s2[],int next[]){
int l1= strlen(s1);
int l2= strlen(s2);
int i=0,j=0;
while (i<l1&&j<l2){
if(s1[i]==s2[j]){
i++;
j++;
}else{
if(next[j]==-1){
i++;
j++;
}else{
j=next[j];
}
}
}
if(j==l2){
cout<<"success!"<<endl;
}else{
cout<<"error"<<endl;
}
}
int main(){
char tmp[]="ABADCABCABADCABD";
char q1[]="ABADCABD";
int next[8];
prefix(q1,next,8);
kmp(tmp,q1,next);
return 0;
}