罗杰斯的博客

kmp算法是模式匹配中的经典算法，在处理很多和字符串的问题时都会用到。不过这个算法虽然实现起来很简单，思路想要描述清楚却不容易，网上有很多资料，但感觉都讲的不太清楚，有些代码都是错误的。为了验证自己已经弄清楚了，决定从头开始介绍这个算法。

假定T为待匹配的文本，P为模式。假定T为ababaabcbab，P为ababaca。我们先从T的第一个字符开始匹配起，粗体表示匹配失败的字符

T a b a b a a b c b a b
P a b a b a c

如果按照朴素的匹配算法，那我们下次应该就从第二个字符开始匹配。那有没有更快一些的方法呢？观察一下P，前两个字符分别和第三、第四个字符相等，也就是说如果我们下次可以从T的第1+2，也就是第三个字符开始匹配起。也就是说假定P[1...q] = T[s + 1...s+q]，那么满足P[1...k]=T[ss + 1... ss + k] 的ss最小是多少，其中ss + k = s + q。

进一步地解释，假定匹配在T的第t位和P的第p位失效了，那么我们接下来要继续比较T的第t位和P的(p-x)位，相当于把P往右移了x位。那么如果我们能知道p-x的值，整个匹配过程就很好理解了，t每次增大1，当匹配失效时置p为p-x，继续匹配。

如何知道p-x的值呢？我们先考察一下它的意义，匹配失败并重置p为p-x后我们可以继续比较T的第t位和P的p-x位，这说明在这位之前，t的长为p-x-1的左串等于P的长为p-x-1的前缀。事实上这就是p-x的定义。对于所有的p，记其p-x的值为向量next。那么给定P，对于其中的第i位来说，如果P[i-k+1...i]和P[1...k]相等，且k < i，则next[i] = k。

求next向量的过程可表示如下，先初始化next[0]为0，假设我们已经知道next[i-1] = k，求next[i]。
1. 如果P[k + 1] = P[i]，则next[i] = k + 1
2. 如果P[k + 1] != P[i] 并且 k > 0，则令k = next[k] 直到P[k + 1] = P[i]或 k = 0
3. 第2步得到了新的k，如果P[k + 1] = P[i]，那么next[i] = k + 1，否则为k。

完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

#define MAX 10000

void
gen_next(char *p, int *next)
{
    int len = strlen(p);

    *next = 0;
    int k = 0;
    int i = 1;

    for (i = 1; i < len; i ++) {
        while (k > 0 && *(p + k) != *(p + i))
            k = *(next + k);
        if (*(p + k) == *(p + i))
            k ++;
        *(next + i) = k;
    }

    // We can set next[0] to -1 to make the code simpler
    // *next = -1;
}

int
find(char *p, char *q)
{
    assert(p && q);

    int *next, lenq = strlen(q), lenp = strlen(p), count = 0;
    next = (int *)malloc(sizeof (int) * lenq);
    if (next == NULL)
        return -1;
    memset(next, 0, sizeof (int) * lenq);

    gen_next(q, next);

    int pi, qi;
    pi = qi = 0;
    while (pi < lenp && qi < lenq) {
        // If next[0] == -1, the while loop can be writen is this way
        //
        // if ((*(p + pi) == *(q + qi) || qi == -1) && pi < lenp && qi < lenq)
        //     pi ++, qi ++;
        // else
        //     qi = *(next + qi);
        while (*(p + pi) == *(q + qi) && pi < lenp && qi < lenq)
            pi ++, qi ++;
        if (qi == lenq) {
            printf("found one match, begins at %d\n", pi - lenq);
            count ++;
            qi = *(next + qi - 1);
            continue;
        }
        if (qi == 0) {
            pi ++;
        }  else {
            qi = *(next + qi);
        }
    }

    return count;
}

int
main(int argc, char **argv)
{
    char s[MAX] = "ababab";
    char p[MAX] = "abab";

    printf("total %d match\n", find(s, p));

    return 0;
}