概述

• 在字符串查找的过程中，如果某个字符匹配失败，不该完全跳过所有已经匹配的字符重新搜索。
• KMP 算法的主要思想是提前判断如何重新开始查找，而这种判断只取决于模式本身。¹

模式指针的回退

\(dfa[txt.charAt(i)][j]\) 是在比较了 \(txt.charAt(i)\) 和 \(pat.charAt(j)\) 之后应该和 \(txt.charAt(i + 1)\) 比较的模式字符位置。

当 \(txt.charAt(i)\) 和 \(pat.charAt(j)\) 匹配时，\(dfa[txt.charAt(i)][j] = j + 1\)，否则，右移模式字符串，直到和 \(pat[0:i]\) 匹配或不能匹配为止，匹配的重叠字符个数即为 \(dfa[txt.charAt(i)][j]\) 的新值，这也是有些文章中讲的真前缀集合跟真后缀集合交集的元素的最大长度的含义。

KMP 查找算法

基于上面的 DFA，就能很容易地构造出 KMP 子字符串查找算法了：

int txt_len = strlen(txt);
j = 0;

for (i = 0; i < txt_len && j < pat_len; i++) {
    j = dfa[txt[i]][j];
}

if (j == pat_len) {
    return i - pat_len;
} else {
    return -1;
}

DFA 模拟

确定有限状态自动机（DFA）的状态表示模式字符串的索引值，并根据所在状态和当前需要匹配的文本字符进行状态转移。例如下面和模式字符串A B A B A C对应的确定有限状态自动机：

构造 DFA

我们按照状态（模式字符串下标）\(j\) 从小到大的顺序构造 DFA。

显然，\(dfa[pat.charAt(0)][0] = 1\)，其他字符都为 0。

\(dfa[][1]\) 只有在碰到 \(pat.charAt(1)\) 的时候等于 2，其余情况匹配失败，需要右移模式字符串一位重新匹配，此时和 \(dfa[][0]\) 的结果一致。

\(dfa[][2]\) 只有在碰到 \(pat.charAt(2)\) 的时候等于 3，其余情况匹配失败，需要右移模式字符串一位重新匹配，此时就和 \(dfa[][dfa[pat.charAt(1)][0]]\) 的结果一致。

更加一般的，在构造 \(dfa[][j]\) 的时候，如果碰到 \(pat.charAt(j)\)，则 \(dfa[][j] = j + 1\)，否则，需要右移模式字符串一位重新匹配，此时就和 \(dfa[][dfa[pat.charAt(j - 1)][dfa[pat.charAt(j - 2)][...]]]\) 的结果一致。

这里可以简化 dfa 的列下标为 \(X\)，他的转移方程如下：

最后，也是关键的一点是概念上讲，\(X\) 表示模式字符串右移一位后匹配的字符长度，所以 \(X < j\)，从而确保了在构建 \(dfa[][j]\) 的过程中只需要依赖已经构建好的部分，保证了算法的正确性。

构建代码如下所示：

dfa[pat[0]][0] = 1;
int x = 0;
for (i = 1; i < pat_len; i++) {
    for (j = 0; j < char_num; j++) {
        dfa[j][i] = dfa[j][x];
    }
    dfa[pat[i]][i] = i + 1;
    x = dfa[pat[i]][x];
}

总结

总的来说，KMP 算法是普通暴力算法的一种优化方案，只有在文本字符串中包含大量重复子串时才能获得较大收益。但是由于其不需要回退文本字符串指针，所以没有了回退带来的开销，非常适合用在长度未知不可回退的输入流中。

完整的算法实现如下：

int KMP(char *txt, char *pat)
{
    int char_num = 256;
    int pat_len = strlen(pat);
    int i;
    int j;

    if (pat_len == 0) {
        return 0;
    }

    // Build DFA from pattern
    int **dfa = calloc(char_num, sizeof(int *));
    for (i = 0; i < char_num; i++) {
        dfa[i] = calloc(pat_len, sizeof(int));
    }

    dfa[pat[0]][0] = 1;
    int x = 0;
    for (i = 1; i < pat_len; i++) {
        for (j = 0; j < char_num; j++) {
            dfa[j][i] = dfa[j][x];
        }
        dfa[pat[i]][i] = i + 1;
        x = dfa[pat[i]][x];
    }

    // Simulate operation of DFA on txt
    int txt_len = strlen(txt);
    j = 0;

    for (i = 0; i < txt_len && j < pat_len; i++) {
        j = dfa[txt[i]][j];
    }

    if (j == pat_len) {
        return i - pat_len;
    } else {
        return -1;
    }
}