kmp算法由浅入深：一行代码引发的无限思考

KMP算法动画

动画先行。

KMP算法是什么

KMP算法是Knuth-Morris-Pratt字符串查找算法，以创作者们的名字首个大写字母命名，用于处理字符串查找问题。

这个算法由高德纳和沃恩·普拉特在1974年构思，同年詹姆斯·H·莫里斯也独立地设计出该算法，最终三人于1977年联合发表。

KMP的代码量非常少，看起来并不复杂，然而这个算法极度晦涩，之前我们见过快速排序算法和Knuth随机算法的精巧，然而KMP算法除了与其类似的精巧，其中蕴含的原理却不容易理解，特别是这一句：

k = prefix[k]

字数越少，事情越大。

虽然只有几个字符，却是本篇的讨论核心。先上C++代码。

C++源码

// 计算kmp前缀表，用于匹配失败后进行回退操作
std::vector<int> compute_prefix_function(std::string& p)
{
    int n = p.length();
    std::vector<int> prefix(n);

    prefix[0] = -1;
    int j = 0;
    int k = -1;

    while (j < n - 1) {
        if (k == -1 || p[k] == p[j]) {
            // 如果相同，则记录当前k的位置
            k++;
            j++;
            prefix[j] = k;
        } else {
            // 不同则回退
            k = prefix[k];
        }
    }

    return prefix;
}

int kmp_matcher(std::string& t, std::string& p)
{
    auto prefix = compute_prefix_function(p);

    int j = 0;
    int k = 0;

    while (j < t.length() && k < p.length()) {
        if (k == -1 || t[j] == p[k]) {
            // 相同则前进
            k++;
            j++;
        } else {
            // 不同则回退尝试
            k = prefix[k];
        }
    }

    if (k == p.length()) {
        return j - p.length();
    }
    return -1;
}

上面代码参考算法导论，并做了一些调整，看起来会精简一些。

KMP算法的原理

在算法导论第32章，讨论了4种字符串匹配算法，第一种是朴素字符串匹配，第二种是Rabin-Karp算法，第三种是有限自动机，第四种是KMP算法。

字符串匹配中，设文本为t，待匹配字符串为p，朴素算法是遍历t中的每一个子串，然后和p进行比较，复杂度

。第二种算法性能很好，原理是数论哈希，通过预处理t中子串的hash值，然后和p的hash进行比较，复杂度是

。第三种是有限自动机，也就是DFA，首先将p预处理成一个DFA，然后将t进行输入，时间复杂度

。

而KMP算法是有限自动机（DFA）的改进版本，DFA五要素中转移函数

用于改变状态，KMP算法通过生成一张前缀表，计算时间复杂度

，简化了DFA的转移函数

，这里q是状态，a是输入符号。

上面代码中compute_prefix_function函数的功能就是计算前缀表，我们使用动画视频中的字符串来说明这个是如何运作的。

对于字符串cbccbcbccb，要如何求出前缀表（有些文章称之为next表）呢？

其实是依次取得字符串前缀字符串，然后看前缀与后缀字符相同的个数，如下图所示：

左边红色部分就是前缀表，大脑很容易计算这个问题，但是对于计算机，需要进行规约：如何求取一个字符串的所有前缀

的最长相同前后缀字符数？

朴素解法：对于每一个前缀

，从1个前缀数开始判断后缀是否与前缀相同，复杂度

。

KMP算法的精巧之处就在于在

时间复杂度上解决这个问题。

可以将KMP算法看做是一个双指针问题，每次遍历如果p[k]和p[j]相同，就前移2个指针，如果不相同，就回退指针k。数组默认为0，相同的时候增加k的值。

回退的时候是k=prefix[k]，这是为什么呢？为什么不是k=0？

我在学习kmp算法的时候，刚开始百思不得其解，用了很多时间去找答案，然而却很少有文章专门讲这个问题，看算法导论里面的讲解完全是一脸懵逼。

直到我自己在纸上画了一个简单的图：

总结一下就是，每次遇到不能继续前进的字符a，那么就看当前匹配到哪里了，然后把这个匹配进度回退到开头，其实就是把后缀变成前缀s，试探a能否被s接纳，如果能接纳，那么a的状态值就是s最后一个字母的状态值+1，如果不能接纳，那么继续重复试探。一直失败会回退到-1，那么a的状态值就是默认的0。

这是弄清楚KMP算法的第一步！

如果你能理解这些，那么你对KMP的原理已经掌握了一半，接下来让我尝试着使你能理解剩下的一半。

KMP算法与正则表达式

KMP算法是从DFA来的，我们大学课本里面可能只有编译原理这门课会比较详细的介绍DFA， 同时也会介绍正则表达式和NFA，一般来说正则表达式都是转化为NFA在再转成DFA，但是普通字符串的匹配问题没有复杂的正则符号，所以我们可以很容易的写一个字符串ababbcaababac的状态转移图：

每一个状态都是字符串p的前缀，q0表示起始状态，是空串，q13是接受状态（也称为结束状态），这里面没有标注分支，只是画了主干，比如状态q4是abab，可以画一条线接受a到q1，这里画了从q11回退到q4，q12回退到q3，其实前缀表中的数值就是回退后的前缀所在的状态值，KMP的前缀表是一个精简的DFA状态转移表。DFA在状态转移过程中会产生多条分支，KMP虽然只记录了一个值，却是嵌套回退的，优先匹配最大值，也因此可能产生多条分支。

这就是KMP算法前缀表的DFA理解，状态之间的转换不是遇到不同就回退到初始状态，而是可以进入一个中间状态。

kmp算法

kmp的前缀表通过p与p之间的比较来计算的，自底向上的进行，而matcher函数则是t与p进行比较，比较方法与前缀表的比较非常相似，在遍历过程中，如果字符相同则前进，否则通过前缀表进行回退，通过上面的学习，我们知道这种回退是计算dfa其他分支，如果没有分支会回退到起始状态0，这样理解起来就非常清晰了。

结，到这里就算是kmp算法的结尾了，本文主要是探讨回退问题，具体细节还需要读者在理解的基础上进行完善。

尾笔

最近在看计算理论的书，顺便在这里唠唠嗑，有闲情的继续往下看。

KMP算法与计算理论

kmp算法的原理是dfa，dfa这个概念其实是计算理论的内容，只不过编译原理里面恰好用到了词法和文法解析。事实上，小编认为如果先学习计算理论这门课，再学习编译原理的知识会简单很多，计算理论是一门非常系统的课程，主要分为三大模块，第一部分是自动机和语言，第二部分是可计算性理论，第三部分是计算复杂性理论，通过学习计算理论，我们可以知道哪些计算机问题是可以计算的，哪些是不可以计算的，以及确定一个问题的计算复杂度。

这样看可能没啥特别，确实，因为这是计算机的理论部分，不是学一点就能立竿见影的出成果，但是学好这个能够提高分析问题的能力。既然是理论，学习的时候就需要把这三个模块的知识全部推导出来，从dfa开始，到nfa、正则表达式、下推自动机、图灵机、复杂度等，这些问题都是通过数学的方式进行分析，工作量会非常大。

计算理论英文是tcs，目前市面上相关资料非常少，唯一的一本经典叫做《理论计算导引》，非常适合新人。国内理论计算研究方向上代表人物姚期智，姚先生的学术贡献毫无疑问是极富开创性且影响深远的， 主要集中在密码学基础，计算复杂性及量子计算方面，比如他首次证明了量子图灵机模型与量子电路模型的等价性。

国内能带好这个导师估计也是凤毛麟角，做这方面研究的童鞋更多的需要名校导师带和自己悟，普通本科生看看理论计算导引就挺好的了。

全文结。