KMP匹配算法源码

谁借莪１个温暖的怀抱￠ 2022-06-07 01:43 131阅读 0赞

模式匹配问题，即字符串的匹配，int index(String t,String p)，求p在t中第一次出现的位置。如何高效地匹配？先来讨论朴素的回溯的模式匹配。例如，设t=“abbaba”，p=“aba”，p的长度为6（plen=6），t的长度为3（tlen=3）。匹配过程如下：

![20180306145128995][]

算法如下：

int index(string p, string t)
    {
        int i = 0, j = 0;           //i，j分为p，t串当前字符的下标
        while(i<p->n && j<t->n){    //反复比较
            if(p->c[i] == t->c[j]){
                i++; j++;           //继续匹配下一个字符
            }
            else{
                j = j - i + 1;      //p，t串的i，j回溯，即重新开始下一次匹配
                i = 0;
            }
        }
        if(i >= p->n)
            return(j - i +1);       //匹配成功，返回p中第一个字符在t中的序号
        else
            return 0;               //匹配失败
    }

这种算法效率不高，在最坏的情况下，每趟比较都在最后出现不等，最多比较 tlen-plen+1 趟，总比较次数为 plen×（tlen-plen+1），由于在一般情况下plen<<tlen，所以算法的运行时间为O（plen× tlen）。

对于上图的匹配过程，由（a）可知：p0=t0，p1=t1，p2！=t2，

由p0！=P1可知p0！=t1，将p右移一位后（b）的比较一定不等；

由p0==p2可知p0！=t2，将p再右移一位后（c）的比较一定不等；

因此，由（a）便可直接将p右移3位跳到（d），从p0和t3开始作比较，很快可以匹配成功。这样的匹配过程对字符串 t 就消除了回溯。

这种快速的算法也就是，在右移若干位后，立即用p串中的一个新的字符Pk（k<i）和tj（甚至t（j+1））继续作比较。Knuth等人发现这个k值不仅存在，而且仅依赖于p串本身，与t串无关，因此可以在与任何串匹配前计算出k值。

假设k值已经存在，存放在数组next中，next\[ i \] 表示与pi对应的k值。意义就是，一旦匹配过程中发现pi！=tj，可用p中以next\[ i \]为下标的字符Pnext\[ i \] 与tj作比较。特别地，当p中任何字符都不能和tj比较时（此时next\[ i \]==0），直接从t（j+1）和p0作比较。将上面的算法部分改变：

while(i<p->n && j<t->n){    
            if(i == -1){
                i++; j++;            //i变为0，即t(j+1)和p0作比较
            }
            else if(p->c[i] == t->[j]){
                i++; j++;
            }
            else
                i=next[i];
        }

可以合并，

while(i<p->n && j<t->n){    
            if(i == -1 || p->c[i] == t->[j]){
                i++; j++;            //i变为0，即t(j+1)和p0作比较
            }
            else
                i=next[i];
        }

分析其时间复杂度，由于 j 只增不减，j++最多执行n次，从而相邻的 i++最多也不超多n次；循环中唯一能使 i 减少的语句是 i=next\[ i \]，而使i=-1，那么下步必定会执行\{ i++; j++;\}，所以 i=next\[ i \]语句的执行次数不会超过i++的执行次数加一。因此，该算法的事件代价为O（n）。

那么怎样计算next数组呢？

我们发现，在p与任意目标t匹配时，若pi≠tj，则意味着pi之前的字符已与t中对应的字符相等。因此，如下图(a)和(b)是等价的。

![20180307092256329][]

然后，将p右移i-k位，希望用pk与tj继续比较，这意味着tj以前的比较工作都已全部相等，相当于p0…p(i-1)的一个前缀p0…p(k-1)与它的一个后缀p(i-k)…p(i-1)长度相等。如图，

![20180307093137655][]

因此，在p0…p(i-1)中，求出其相同的而且是最长的前缀和后缀，设长度为k(0≤k≤i-1)，这个值仅仅依赖于p本身，与任何t无关。

①当右移量为i-k时，相同的前后缀恰好对齐，pk与tj对齐。用不着再去比较这一对相同的前后缀；

②当右移量小于i-k时，也用不着去比较，因为根据k的意义，长度大于k的前后缀必定不相等；

③当右移量大于i-k时，又可能错过匹配成功的机会。

通过上面的分析，可以知道求next数组的关键，就是求出p0…p(i-1)中最大的相同的前后缀的长度。而求出这个长度，也就是判断p0…p(i-2)是否等于p1…p(i-1)，如果不等，则继续判断p0…p(i-3)是否等于p2…p(i-1)等等。显然，这实际上还是模式匹配问题。

作为一种特殊情况，当i=0时，令next\[0\]=-1，因为p0与tj比较不等，只能用p0与t(j+1)去比较。另外，如果p0…p(i-1)的最大相同的前后缀长度为k，那么p0…pi的最大相同的前后缀长度就为k+1。加上有next\[0\]=-1的基础，就可以依次计算出next\[1\]，next\[2\]…next\[n-1\]。在计算next\[i+1\]时，充分利用已经求出的next\[0\]，next\[1\]…next\[i\]的值，使得计算next\[i+1\]的过程有点类似于前面的无回溯的模式匹配问题。算法如下:

void makeNext(PSeqString p, int *next)
    {
        int i = 0, k = -1;           //初始化
        next[0]=-1;
        while(i < p->n - 1){         //计算next[i+1]
            while(k >= 0 && p->c[i] != p->c[k])
                k=next[k];
            i++; k++;
            next[i] = k;
        }
    }

算法改进，试想，按上面算法求出k后，若pk=pi，则当发现pi≠tj时，用pk和tj比较，也必然不相等，应该再右移，用Pnext\[i\]与tj比较。既然预先知道这种情况，理应预先避免走这个弯路，使得next\[ i \]的值尽可能变得更小，以便在匹配时更多地右移。如此，当发现pi≠tj时，则右移i+1位，用p0与t（j+1）开始比较。即将 next\[i\] = k 改为：

if(p->c[i] == p->c[k])
            next[i] = next[k];
        else
            next[i] = k;

算法分析，从表面上看，有两层循环，每重循环最多执行m次，最大的运行时间可能达到O（m^2），但仔细分析，因为每执行一次最外层循环，i 严格增加1，所以最外层循环正好执行 m-1 次；另外k值从-1开始，执行 k+m-1 次（i++; k++;），并且只有在这一语句中k被增值。在内层循环中，语句k=next\[k\] 至少使d减少1，所以整个算法中，这个语句执行次数不可能超过m-1次（否则k将小于-1，不可能），所以最内层循环的执行次数最大为 m-1 。

因此，该算法的时间代价为O（m），与无回溯的模式匹配模式合在一起，即用长度为m的模式串p与长度为n的目标串t进行匹配，所需的时间为O（m+n），算法如下：

int index(PSeqString p, PSeqString t, int *next)
    {
        int i = 0, j = 0;           //i，j分为p，t串当前字符的下标
        
        while(i<p->n && j<t->n){    
            if(i == -1 || p->c[i] == t->[j]){
                i++; j++;            //i变为0，即t(j+1)和p0作比较
            }
            else
                i=next[i];
        }
        
        if(i >= p->n)
            return(j - i + 1);       //匹配成功，返回p中第一个字符在t中的序号
        else
            return 0;               //匹配失败
    }
    
    void makeNext(PSeqString p, int *next)
    {
        int i = 0, k = -1;           //初始化
        next[0]=-1;
        while(i < p->n - 1){         //计算next[i+1]
            while(k >= 0 && p->c[i] != p->c[k])
                k=next[k];
            i++;
            k++;
            if(p->c[i] == p->c[k])
                next[i] = next[k];
            else
                next[i] = k;
        }
    }

当n>>m时，该算法的优越性更显然，特别是当一个模式p被反复使用时，只要花一次O（m）的时间代价计算next数组，以后的每次匹配只要用O（n）的时间；但是，当n和m相差不大时，并且只匹配一次就能成功时，朴素的回溯的算法更快。

下面是一个例子的完整代码（部分变量储存方式已改变）：

#include <iostream>
    
    using namespace std;
    
    int index(string p, string t, int lenP, int lenT, int *next)
    {
        int i = 0, j = 0;           //i，j分为p，t串当前字符的下标
    
        while(i<lenP && j<lenT){
            if(i == -1 || p[i] == t[j]){
                i++; j++;            //i变为0，即t(j+1)和p0作比较
            }
            else
                i=next[i];
        }
    
        if(i >= lenP)
            return(j - i + 1);       //匹配成功，返回p中第一个字符在t中的序号
        else
            return 0;               //匹配失败
    }
    
    void makeNext(string p, int lenP, int *next)
    {
        int i = 0, k = -1;           //初始化
        next[0]=-1;
        while(i < lenP - 1){         //计算next[i+1]
            while(k >= 0 && p[i] != p[k])
                k=next[k];
            i++;
            k++;
            if(p[i] == p[k])
                next[i] = next[k];
            else
                next[i] = k;
        }
    }
    int main()
    {
        string p, t;
        cout<<"Input P string:\n";
        cin>>p;
        cout<<"Input t string:\n";
        cin>>t;
        int len = p.length();
        int next[len];
        makeNext(p, len, next);
        cout<<"The begin position is "
            <<index(p, t, len, t.length(), next);
    }

结果样例：

Input P string:
    ANOTONY
    Input t string:
    abcdefANOTONYghijANTONYsfj
    The begin position is 7

模式p在目标t中第一次出现的位置是第7个字符。

[20180306145128995]: /images/20220607/70e7b0ad4e924297b28b52dd8a002633.png
[20180307092256329]: /images/20220607/3430c929f0524dcc8655cbcc2162920b.png
[20180307093137655]: /images/20220607/4570b196cdd449cdacfa1b016024c278.png