KMP算法：详解

匹配

很简单，用next[x]表示前移数组。

// 伪代码
while(!complete()) {
    if(match(c[i], str[j]))
        i++,j++;
    else
        i = next[i];
}
return j+1-len(c);

next[i]的生成

匹配过程事实上非常简单，难的是next[x]的生成。

思路：用两个迭代器，递归思想。

记号：用c[x]表示待处理字符串，用next[x]表示前移数组。

朴素next生成算法

这样求出来的next[x]有以下性质：

1. c[0]=>c[next[x-1]]的字符串匹配c[x-1-next[x-1]]=>c[x-1]的字符串
2. next[x]是满足以上条件的最大值

从这一表达式可以看出，next[x]从数学上难以直观求解。

注：有人使用“前缀”“后缀”来表示1.条件，令人十分不习惯，还需要进一步翻译成数学语言，太不直接

使用两个迭代器i,k其中i在前，k在后。每一次迭代的结果是求出next[i+1]。上一次迭代之后，显然i=i+1，k应当满足：

1. 处于这样一个位置，即“从c[0]到c[k]的字符序列完全匹配从c[i-k]到c[i]的字符序列”。比如，"abab"k=2, i=4或者"aaaa"k=3,i=4。容易验证，空串(k=-1,i=0)满足这个状态。
2. k是满足条件1.的最大可能值。

满足这一条件时，考虑next[i+1]，可见直接让next[i+1]=k+1，我们便满足了next[x]的两条性质。且慢！这里要使递归进行下去，还要使末态满足下面两条性质。怎么做呢？

若c[i+1]==c[k+1]是最皆大欢喜的事情。这时k=k+1自然满足条件。次好的事情是k==-1，如果c[i+1]==c[0]不满足，只要继续让k=-1就好了。不然的话怎么弄呢？需要减少匹配的字符数。本质上，这又是一个c与自己的匹配！这么考虑：“从c[0]到c[k]的字符序列完全匹配从c[i-k]到c[i]的字符序列”，c[i+1]==c[k+1]不满足。于是移动c，从下一个可能的匹配位置开始匹配，直到“从c[0]到c[k']的字符序列完全匹配从c[i+1-k']到c[i+1]的字符序列”.

// 循环内部
next[i+1]=k+1;
if(c[k+1]==c[i+1])
    k++;
else {
    if(k==-1)
        // 什么也不做
    else {
        k = k+1-KMP(c, c+i-k); // 伪代码，被匹配者最大到c+i+1
    }
}
i++;

// 上面伪代码事实上包括了特殊情况，自行验证一下！
// 循环内部
next[i+1]=k+1;
k = k+1-KMP(c, c+i-k);
i++;

我们试着把匹配过程写开。

next[i+1]=k+1;
m=0, n=0;
while(true) {
    if(c[m]==c[i-k+n]) {
        /* if(m>i) break; */ //不可能发生
        if(n>k+1) break; // n==k+2
        m++,n++;
    }
    else {
        m=next[m];
        if(m==-1) break;
    }
}
// k=k+1-((k+2)-(m+1))
k=m;
i++;

这种写法未免过于复杂。事实上，第一趟匹配中，c[0=>k]其实都是匹配好的。可以借此简化代码：

next[i+1]=k+1;
m=k+1, n=k+1;
while(m!=-1 && n<=k+1) {
    if(c[m]==c[i-k+n])
        m++,n++; // 事实上循环直接跳出了
    else
        m=next[m];
}
k=m;
i++;

我们发现变量n其实是多余的。

next[i+1]=k+1;
m = k+1;
while(m>=0 && c[m]!=c[i+1])
    m=next[m]; // k=next[k+1]-1
k=m;
i++;

m也是多余的。把上面的代码改写一下，成为如下简单形式：

while(k>=0 && c[k]!=c[i])
    k=next[k];
i++,k++;
next[i]=k;

优化的next生成算法

next数组满足的条件为：

1. c[0]=>c[next[x-1]]的字符串匹配c[x-1-next[x-1]]=>c[x-1]的字符串
2. c[x]!=c[next[x]]
3. next[x]是满足以上条件的最大值

上面的算法脑抽了，要想匹配少，显然k越小越好。比如，要匹配"abababac"，仅考虑前5位，next[5]应该为3. 但第6位b不匹配，第4位b也不可能匹配。这就其实可以进一步减小k的值，只需要加一个判断：

while(k>=0 && c[k]!=c[i])
    k=next[k];
i++,k++;
if(c[i]==c[k])
    next[i]=next[k];
else
    next[i]=k;

用数学归纳法可以证明，优化的这一算法生成的next[x]满足上面三点条件。

完整代码(C语言)

// KMP
#define MAX_LEN 50
typedef struct
{
    char c[MAX_LEN];
    int n;
} SeqString, *pSeqString;

void makeNext(pSeqString p, int next[])
{
    int i = 0, k = -1;
    next[0] = -1;

    while (i < p->n - 1)
    {
        while (k >= 0 && p->c[i] != p->c[k])
            k = next[k];
        i++;
        k++;
        // next[i] = k;
        if (p->c[i] == p->c[k])
            next[i] = next[k];
        else
            next[i] = k;
    }
}

int pMatch(pSeqString t, pSeqString p, int next[])
{
    int i = 0, j = 0;
    while (i < p->n && j < t->n)
        if (i == -1 || p->c[i] == t->c[j])
        {
            i++;
            j++;
        }
        else
            i = next[i];
    if (i >= p->n)
        return (j - p->n + 1);
    else
        return 0;
}

扩展

KMP算法的匹配，思想和“状态机”有一定的相似性。两个迭代器对应的字符进行比较，失败则改变一下“状态”，改变的方式由next[x]数组定义。KMP算法的一种进阶形式是AC自动机算法，可以处理更加复杂的多维匹配问题。