KMP算法

KMP算法

KMP算法是一种模式匹配算法，可以尽量减少主串与模式串的匹配次数

算法步骤

1.生成next数组（前缀表）

例如字符串：ABADCABD

所以生成前缀表数组为[0,0,1,0,0,1,2]

原因：

例如AB，前缀和后缀分别为A和B，并部相同，所以最长公共前后缀为0；例如ABA，前缀和后缀分别为，A，AB，后缀：A，BA，所以最长的公共前后缀长度为1；....

例如ABADCAB，最长公共前后缀为AB，长度为2

代码实现：

#include <iostream>
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 B C A B A A B A D C A B D

子串：A B A D C A B D next数组为：[-1,0,0,1,0,0,1,2]

例如，当主串与子串第八个不相同时候，那么按照暴力方法，子串和主串都将回溯到第二个进行重新比较，而有了next数组，则可以利用数组对照第八个元素值为2，那么只需要j回溯到子串第二个元素，并将该元素与当前不相同的位置对其即可继续进行比较。

如果连续匹配失败的话，那么就将最长公共前缀数组前移一位，相当于最长公共前缀长度-1，并跳转到相应的元素再进行比对，直至达到第一个数组时候，值为-1，那么就整体子串和主串均向后移动一位

KMP完整算法

#include <iostream>
#include <stdio.h>
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;
}