不再遗忘——KMP算法详解

Leetcode28. 讲述了这样一个问题：

也许你早已听闻kmp算法的大名，甚至和我一样学习过敲过很多次了，可是时间一长总是会忘。我很不甘心，于是在这篇知乎回答的基础上（https://www.zhihu.com/question/21923021/answer/281346746 ，答主海纳）对代码进行了改进，在文章中也添加了自己的理解。话不多说，我们这就开始。

1.朴素算法

如果你压根不知道什么kmp，只凭原始本能进行暴力枚举呢？这当然是可以的。为了方便表述，我们把题目中haystack代表的字符串定为主串，needle代表的字符串定为匹配串。那么最直观的解法是：枚举主串中的每个字符作为「发起点」，每次从主串的「发起点」和匹配串的「首位」开始尝试匹配：

若匹配成功：继续匹配，主串和匹配串索引同时向前。
若匹配失败：枚举主串的下一个「发起点」，匹配串索引重新移到「首位」，并重新尝试匹配。（重点注意此处与kmp的不同）

叽里咕噜说再多，其实也就是两层循环的事：

class Solution {
public:
    int strStr(string s, string p) {
        int n = s.size(), m = p.size();
        for(int i = 0; i <= n - m; i++){
            int j = i, k = 0; 
            while(k < m and s[j] == p[k]){
                j++;
                k++;
            }
            if(k == m) return i;
        }
        return -1;
    }
};

作者：宫水三叶
链接：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/solutions/575568/shua-chuan-lc-shuang-bai-po-su-jie-fa-km-tb86/

在时间复杂度上，内层匹配复杂度为 O(m)，外层遍历复杂度为 O(n−m)，总体就是O((n−m)∗m)。

2.kmp算法

显然暴力算法既不优雅时间又长，改进势在必行。但是在说kmp算法之前，我们必须先了解字符串前后缀的概念：

如果字符串A和B，存在A=BS，其中S是任意的非空字符串，那就称B为A的前缀。例如，”Harry”的前缀包括{”H”, ”Ha”, ”Har”, ”Harr”}，我们把所有前缀组成的集合，称为字符串的前缀集合。同样可以定义后缀A=SB，其中S是任意的非空字符串，那就称B为A的后缀，例如，”Potter”的后缀包括{”otter”, ”tter”, ”ter”, ”er”, ”r”}，然后把所有后缀组成的集合，称为字符串的后缀集合。要注意的是，字符串本身并不是自己的后缀。

我们知道，很多字符串本身拥有大量的字符重合。比如下面的图1.12，在这两个字符串的匹配过程中，abab经常作为常客出现，若是每次匹配失败都要把整个匹配串重新遍历核对一遍，那真是太不划算了！那么有没有一种改进方法，让循环能够从已经核对无误的字符处开始匹配呢？

你一定想到，若是主串后缀和匹配串前缀有某种记录相同匹配个数的方法，就能大大减少时间了。没错，部分匹配表(Partial Match Table，简称PMT)它来了！

PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度。例如，对于”aba”，它的前缀集合为{”a”, ”ab”}，后缀集合为{”ba”, ”a”}。两个集合的交集为{”a”}，那么长度最长的元素就是字符串”a”了，长度为1，所以对于”aba”而言，它在PMT表中对应的值就是1。再比如，对于字符串”ababa”，它的前缀集合为{”a”, ”ab”, ”aba”, ”abab”}，它的后缀集合为{”baba”, ”aba”, ”ba”, ”a”}，两个集合的交集为{”a”, ”aba”}，其中最长的元素为”aba”，长度为3。你可以自行练习算出图中其他子串的PMT值。

好了，解释清楚这个表是什么之后，我们再来看如何使用这个表来加速字符串的查找，以及这样用的道理是什么。回到图 1.12 ，要在主串”ababababca”中查找匹配串”abababca”。如果在 j 处字符不匹配，那么由于前边所说的匹配串 PMT 的性质，主串中 i 指针之前的 PMT[j −1] 位就一定与匹配串的第 0 位至第 PMT[j−1] 位是相同的。这是因为主串在 i 位失配，也就意味着主串从 i−j 到 i 这一段是与匹配串的 0 到 j 这一段是完全相同的。而我们上面也解释了，匹配串从 0 到 j−1 ，在这个例子中就是”ababab”，其前缀集合与后缀集合的交集的最长元素为”abab”，长度为4。所以就可以断言，主串中i指针之前的 4 位一定与匹配串的第0位至第 4 位是相同的，即长度为 4 的后缀与前缀相同。这样一来，我们就可以将这些字符段的比较省略掉。具体的做法是，保持i指针不动，然后将j指针指向匹配串的PMT[j −1]位即可。

简言之，以图中的例子来说，在 i 处失配，那么主字符串和模式字符串的前边6位就是相同的。又因为模式字符串的前6位，它的前4位前缀和后4位后缀是相同的，所以我们推知主字符串i之前的4位和模式字符串开头的4位是相同的。就是图中的灰色部分。那这部分就不用再比较了。

思路已经明确，但是如果匹配串在 j 位失配，那么 j 指针回溯的位置的其实是第 j −1 位的 PMT 值。为了编程的方便，我们不直接使用PMT数组，而是将PMT数组向后偏移一位。我们把新得到的这个数组称为next数组。下面给出根据next数组进行字符串匹配加速的字符串匹配程序。其中要注意的一个技巧是，在把PMT进行向右偏移时，第0位的值，我们将其设成了-1，这只是为了编程的方便，并没有其他的意义。在本节的例子中，next数组如下表所示。

需要注意的是，next数组的值的含义仍然是匹配串索引的位置，不要误解成其他意思。若我们已知了匹配串的next数组，本题也就变得很简单了：

class Solution {
public:
    int strStr(string haystack, string needle) {
        int m = haystack.length();
        int n = needle.length();
        
        if (n == 0) return 0;
        
        // 构建next数组（使用更简洁的版本）
 		//……………………………………
        
        // KMP主体算法
        int i = 0;  // haystack的索引
        int j = 0;  // needle的索引
        
        while (i < m && j < n) {
            // j == -1 表示needle的第一个字符就不匹配，需要将i后移
            // 或者当前字符匹配成功
            if (j == -1 || haystack[i] == needle[j]) {
                i++;
                j++;
            } else {
                // 字符不匹配，j回退到next[j]位置
                j = next[j];
            }
        }
        
        // 如果j等于n，说明needle完全匹配
        if (j == n) {
            return i - n;  // 返回匹配的起始位置
        }
        
        return -1;  // 没有找到匹配
    }
/*记忆思路：如果匹配成功，两个索引都往前走；如果匹配失败，匹配串索引通过next数组回到前面的某一位置*/

那么next数组怎么得来呢？很简单，只要看成匹配串和自己匹配就可以啦！

具体来说，就是从匹配串的第一位(注意，不包括第0位)开始对自身进行匹配运算。在任一位置，能匹配的最长长度就是当前位置的next值。如下图所示。

求解next数组的程序如下：

void getNext(string p, vector<int>& next) {
    next[0] = -1;  // 初始化为-1，表示没有真前缀
    int i = 0;     // 当前计算next值的位置
    int j = -1;    // 最长相等前后缀的长度（也是回退位置）

    while (i < (int)p.length()) {
        if (j == -1 || p[i] == p[j]) {
            // j == -1：表示已经回退到最开始，没有可匹配的前缀
            // p[i] == p[j]：当前字符与前缀的下一个字符相等
            ++i;
            ++j;
            next[i] = j;  // next[i+1] = j+1
        } else {
            // 当前字符不匹配，j回退
            j = next[j];
        }
    }
}
/*记忆思路：如果匹配成功，两个索引都往前走，并给next数组赋值；如果匹配失败，匹配串索引通过next数组回到前面的某一位置*/

总程序如下：

class Solution {
public:
    void getNext(string p, vector<int>& next) {
        next[0] = -1;  // 初始化为-1，表示没有真前缀
        int i = 0;     // 当前计算next值的位置
        int j = -1;    // 最长相等前后缀的长度（也是回退位置）
        
        while (i < (int)p.length()) {
            if (j == -1 || p[i] == p[j]) {
                // j == -1：表示已经回退到最开始，没有可匹配的前缀
                // p[i] == p[j]：当前字符与前缀的下一个字符相等
                ++i;
                ++j;
                next[i] = j;  // next[i+1] = j+1
            } else {
                // 当前字符不匹配，j回退
                j = next[j];
            }
        }
    }
    int strStr(string haystack, string needle) {
        int m = haystack.length();
        int n = needle.length();
        
        if (n == 0) return 0;
        
        // 构建next数组（使用更简洁的版本）
        vector<int> next(n + 1);
        getNext(needle, next);
        
        // KMP主体算法
        int i = 0;  // haystack的索引
        int j = 0;  // needle的索引
        
        while (i < m && j < n) {
            // j == -1 表示needle的第一个字符就不匹配，需要将i后移
            // 或者当前字符匹配成功
            if (j == -1 || haystack[i] == needle[j]) {
                i++;
                j++;
            } else {
                // 字符不匹配，j回退到next[j]位置
                j = next[j];
            }
        }
        
        // 如果j等于n，说明needle完全匹配
        if (j == n) {
            return i - n;  // 返回匹配的起始位置
        }
        
        return -1;  // 没有找到匹配
    }
};