KMP算法

文章目录[x]
  1. 1:KMP算法
  2. 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

代码实现:

#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;
}
点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像