LeetCode 28. 实现 strStr()：看懂 KMP 算法

本文正在参与掘金团队号上线活动，点击查看大厂春招职位

一、题目描述：

今天要写的这道题是实现十分常用的字符串匹配的函数：LeetCode 28. 实现 strStr()，我将会使用经典的 KMP 算法来写。因为 KMP 算法十分经典，只要你是计算机专业的学生或者对算法有过研究都应该了解过 KMP 算法，所以在本文里，我不会给出严格的证明，主要会侧重于代码的解释，争取让你看懂 KMP 算法。

二、思路分析：

设 $s$ 是给定的字符串，而 $p$ 是需要查找的模式串。朴素的字符串匹配会从 $s$ 的某一位 $i$ 和 $p$ 的第 $0$ 位开始匹配，如果发现不匹配就退到 $s$ 的 $i + 1$ 位和 $p$ 的第 $0$ 位重新开始匹配。

朴素做法里有许多不必要的回退，通过记录 $p$ 本身的一些性质，我们可以减少回退。

不妨把 $p$ 分成 4 个子串， $prefix \mid mid \mid postfix \mid ch$ ，其中 $prefix$ 是 $p$ 的前缀， $postfix$ 是 $p$ 的后缀，它们是相等的，又叫最长公共前后缀， $mid$ 则是它们中间的字符串， $ch$ 表示我们当前要匹配的字符。
如果 $ch$ 和 $s$ 中相应位置 $s[i]$ 并不匹配，那么我们无需从 $p[0]$ 开始重新匹配，直接让 $s[i]$ 和 $mid[0]$ 所在的位置进行匹配即可，因为 $prefix == postfix$ ，所以在 $p$ 移动到 $mid[0]$ 后， $prefix$ 势必和 $s[i]$ 前面的字符串匹配。
同理，我们可以用一个 $next$ 数组来记录每个位置不匹配时 $p$ 应该回退的位置，其中 $next[i]$ 表示 $p[0…i – 1]$ 的最长公共前后缀，特别的， $next[0] = -1$ ，这就是 KMP 算法的核心。注意这里的最长公共前后缀并不是严格意义上的，因为一个字符串也是它本身的前后缀，最长的应该是它本身，这里指的应该是小于它本身的最长公共前后缀。
预处理出 $next$ 数组还需要用到一个技巧，当我们知道 $next[0…i – 1]$ 时如何推出 $next[i]$ 呢? 这个部分我留在了代码的注释里，为了简洁，我在代码注释里使用前缀替代最长公共前缀，后缀亦是如此。

三、AC 代码：

class Solution {
private:
    vector<int> next;
public:
    int strStr(string haystack, string needle) {
        buildNext(needle);
        return match(haystack, needle);
    }

    int match(const string &s, const string &p) {
        const int n = s.length(), m = p.length();
        // 通过 j 的位置来体现匹配是否完成
        // 如果 j == m 肯定都匹配完了，所以在下面的循环中无需回退 i
        int i = 0, j = 0;
        while (i < n && j < m) {
            // 当 j = -1 的时候说明当前位置完全不能匹配
            // 自然而然地 i 就会 ++ 到下一个位置
            if (j < 0 || s[i] == p[j]) {
                ++i, ++j;
            } else {
                j = next[j];
            }
        }
        if (j == m) {
            return i - j;
        }
        return -1;
    }

    void buildNext(const string &p) {
        int len = p.length();
        if (len == 0) {
            return;
        }
        next = vector<int>(len);
        // l 表示前缀末尾的下标，r 则表示后缀末尾的下标
        int l = next[0] = -1, r = 0;
        while (r < len - 1) {
            // 这里的 l，r 是还没 ++ 过的
            // 如果 l < 0，表示 p[0...r] 没有公共前后缀，这样会让 next[r + 1] = 0;
            // 如果 p[l] == p[r] 就表示公共前后缀的长度可以加 1,而 l + 1 后的结果刚好是前后缀的长度
            if (l < 0 || p[l] == p[r]) {
                ++l, ++r;
                next[r] = l;
            } else {
                // 如果以上条件都不满足，我们就需要缩小已经匹配的前后缀的长度
                // 这里让 l = next[l] 的分析和思路分析的第二点类似
                l = next[l];
            }
        }
    }
};
复制代码