KMP 算法 Kunth-Morris-Pratt

Q：KMP是什么鬼，KMP卖的炸鸡还不错

A：你说的是KFC吧

Q：都一样，反正都是卖炸鸡的，最近买一整只黄金脆皮鸡还送中可

A：那吃好勒您

Q：咕噜咕噜。。。

学习Kunth-Morris-Pratt 算法之前，如果读者还不知道什么是有限自动机的话，那理解KMP算法就比较困难，推荐一遍笔者的有限自动机，当然笔者能力有限。https://blog.****.net/giftedpanda/article/details/86774815

Kunth-Morris-Pratt 算法：一种高效的字符串匹配算法，比有限自动机还要高效，有限自动机的时间复杂度为O(n)+O(m∑),而Kunth-Morris-Pratt 算法的时间复杂度为O(n)+O(m)是不是很神奇呢，下面和笔者一起来学习KMP算法吧。
KMP 算法 Kunth-Morris-Pratt

其实KMP算法和有限自动机的算法思想大致是一样的，还是利用的前缀的思想。如上图a所示当偏移为s时匹配上了5个字符，第六个字符是不匹配的，所以我们要考虑下一次偏移，在偏移为s+1时，文本串T的第一个字符不能与模式串P的第一个字符匹配，但是却能与模式串P的第二个字符匹配，所以s+1的偏移时无效的。在偏移为s+2时，有三个字符时匹配的，在一般情况下提前知道这个答案是有用的。

前缀函数：next[q]=max(k,k<p and P(k)为P(q)的后缀） next[q]是P(q)的真后缀的最长前缀。

KMP算法的精髓就是通过迭代来求解前缀函数。

KMP算法就是会提前计算出模式串P与自己匹配的前缀函数，以便得出下一次有效偏移。为什么要这样做呢。假设从偏移s开始匹配当匹配到第K个字符时，第K+1个匹配失败了，我们可以很有效的利用前面的匹配信息，既然前面能匹配上，证明此时文本串的前K的字符和模式串的前K的字符一样，在进行下一次偏移时，要是我们能知道P的前缀与真后缀的最长匹配长度d，我们知道相对应的字符串是匹配的，我们直接滑到那个位置去匹配就行了，就不用在比较前d个字符了。拿图b来说，当前5个字符"ababa"匹配上时，证明此时文本串也是"ababa",下一次我们就直接从P的前缀与真后缀的最长匹配长度d开始匹配，即偏移为s-d，如图c，模式串的前缀"aba"与文本串的“ababa”的最长匹配长度为3，那么下一次的可能有效偏移就为2。既然是模式串P和文本串T匹配上了，那不就是模式串自己吗，所以我们提前预处理模式串P与自己的前缀与真后缀的最长匹配长度不就行了吗，下一次通过前一次无效偏移的最长匹配长度，就能知道下一次的有效偏移是多少。

KMP 算法 Kunth-Morris-Pratt

如上图就是计算next数组即前缀函数的过程，在无效偏移时通过匹配上的字符的个数，就能得出下一次可能的有效偏移是多少。

笔者认为，这些高效的字符串匹配算法都利用了前缀的思想。即知道自己的前缀和真后缀的最长匹配长度是多少，就把前缀和真后缀对其开始匹配，由于之前是匹配上的，前面部分模式串和文本串都是一样的，那么直接提前预处理模式串P的每一个匹配长度下的P的前缀与真后缀的最长匹配长度，就是一次模式串P要和文本串T要对齐开始匹配的位置。

#include<cstdio>
#include<cstring>
using namespace std;
const int maxp=1000+7;
const int maxt=10000+7;
char P[maxp],T[maxt];    //P为模式串   T为模板串
int next[maxp];         //前缀函数
void Compute_Prefix_Function(char* P)      //计算前缀函数的值
{
    int m=strlen(P+1);    //字符串的下标在读取时从1开始的 
    next[1]=0;        //一个字符 不存在真后缀        
    int k=0;          //初始化前缀函数的值为0 即上一次匹配上的长度
    for(int i=2;i<=m;i++){             //迭代求解前缀函数 KMP算法的精髓
        while(k>0&&P[k+1]!=P[i])          
            k=next[k];
        if(P[k+1]==P[i])        //匹配成功
            k=k+1;
        next[i]=k;
    }
    return ;
}
int KMP_Matcher(char* P,char* T)         
{
    int m=strlen(P+1);        //字符串的下标在读取时从1开始的
    int n=strlen(T+1);
    Compute_Prefix_Function(P);
    int q=0;
    for(int i=1;i<=n;i++){
        while(q>0&&P[q+1]!=T[i])          //匹配不成功 寻找更下一个最长前缀
            q=next[q];
        if(P[q+1]==T[i])
            q=q+1;
        if(q==m){
            printf("Pattern occus with shift %d\n",i-m);
        }
    }
}
int main()
{
    while(scanf("%s %s",P+1,T+1)==2){
        KMP_Matcher(P,T);
    }
    return 0;
}

KMP 算法 Kunth-Morris-Pratt

相关推荐