封面画师：Nengoro(ネんごろぅ) 封面ID：74015476

本文参考视频：小马哥教育(SEEMYGO) 2019年恋上数据结构与算法（第二季）

源码仓库：mofan212/data-structure-and-algorithm (github.com)

1. 串匹配算法

1.1 什么是串

串（Sequence），就是日常开发中熟悉的字符串，是由若干个字符组成的有限序列。

比如“thank”串：

对于字符串“thank”来说，其前缀（prefix）、真前缀（proper prefix）、后缀（suffix）、真后缀（proper suffix）信息如下：

名称	内容
前缀	t、th、tha、than、thank
真前缀	t、th、tha、than
后缀	thank、hank、ank、nk、k
真后缀	hank、ank、nk、k

1.2 串匹配算法

比如，查找一个模式串（Pattern）在文本串（Text）中的位置，在 Java 中可以这样做：

String text = "Hello World";
String pattern = "or";
text.indexOf(pattern); // 7
text.indexOf("other"); // -1

几个经典的串匹配算法：

蛮力（Brute Force）
KMP
Boyer-Moore
Rabin-Karp
Sunday

在本文中，将用 tlen 代表文本串 Text 的长度，plen 代表模式串 Pattern 的长度。

2. 蛮力

2.1 基本思路

以字符为单位，从左到右移动模式串，直到匹配成功。

蛮力算法有 2 种常见的实现思路。

2.2 实现方式一

用 pi 表示模式串中正在进行比较的字符的索引，它的取值范围是 $pi \in [0, plen)$ 。

用 ti 表示文本串中正在进行比较的字符的索引，它的取值范围是 $ti \in [0, tlen)$ 。

当 pi 与 ti 指向的字符匹配成功时，pi 与 ti 分别自增一，即：pi++; ti++;。比如：

当 pi 与 ti 指向的字符匹配失败时，pi 重置为 0，ti 设置为本次匹配开始时指向位置的下一个位置，即：ti -= pi - 1; pi = 0;。比如：

重复这些操作，直到 pi 指向的模式串中的最后一个字符与 ti 指向的字符匹配成功，此时 pi == plen。比如：

public static int indexOf(String text, String pattern) {
    if (text == null || pattern == null) return -1;
    char[] textChars = text.toCharArray();
    int tlen = textChars.length;
    if (tlen == 0) return -1;
    char[] patternChars = pattern.toCharArray();
    int plen = patternChars.length;
    if (plen == 0 || plen > tlen) return -1;

    int pi = 0, ti = 0;
    while (pi < plen && ti < tlen) {
        if (patternChars[pi] == textChars[ti]) {
            ti++;
            pi++;
        } else {
            ti -= pi - 1;
            pi = 0;
        }
    }
    return pi == plen ? ti - pi : -1;
}

在上述实现中，可以在恰当的时候提前退出，减少比较次数。比如：

因此，ti 的退出条件可以从 ti < tlen 修改为：ti - pi <= tlen - plen。也就是说，文本串中正在匹配的子串的开始索引应该小于开始索引的临界值，否则退出循环。

ti - pi 是指每一轮比较中 Text 首个比较字符的位置。

public static int indexOf(String text, String pattern) {
    if (text == null || pattern == null) return -1;
    char[] textChars = text.toCharArray();
    int tlen = textChars.length;
    if (tlen == 0) return -1;
    char[] patternChars = pattern.toCharArray();
    int plen = patternChars.length;
    if (plen == 0 || plen > tlen) return -1;

    int pi = 0, ti = 0, lenDelta = tlen - plen;
    while (pi < plen && ti - pi <= lenDelta) {
        if (patternChars[pi] == textChars[ti]) {
            ti++;
            pi++;
        } else {
            ti -= pi - 1;
            pi = 0;
        }
    }
    return pi == plen ? ti - pi : -1;
}

2.3 实现方式二

用 pi 表示模式串中正在进行比较的字符的索引，它的取值范围是 $pi \in [0, plen)$ 。

用 ti 表示每一轮比较中文本串中首个比较字母的索引，它的取值范围是 $ti \in [0, tlen - plen]$ 。

在这种情况下，可以使用 ti + pi 表示文本串正在进行比较的字符的索引。

当 pi 与 ti + pi 指向的字符匹配成功时，pi 自增一，即：pi++，但 ti 保持不变。比如：

当 pi 与 ti + pi 指向的字符匹配失败时，pi 重置为 0，ti 自增一，即：pi = 0; ti++;。

重复这些操作，直到 pi 指向的模式串中的最后一个字符与 ti + pi 指向的字符匹配成功，此时 pi == plen。比如：

public static int indexOf(String text, String pattern) {
    if (text == null || pattern == null) return -1;
    char[] textChars = text.toCharArray();
    int tlen = textChars.length;
    if (tlen == 0) return -1;
    char[] patternChars = pattern.toCharArray();
    int plen = patternChars.length;
    if (plen == 0 || plen > tlen) return -1;

    int tiMax = tlen - plen;
    for (int ti = 0; ti <= tiMax; ti++) {
        int pi = 0;
        for (; pi < plen; pi++) {
            if (textChars[ti + pi] != patternChars[pi]) break;
        }
        /*
         * pi 有两种可能：
         * 1. 由于前面的 break 然后走到这，此时 pi != plen
         * 2. 前面的 for 循环结束，自然退出，此时 pi == plen
         */
        if (pi == plen) return ti;
    }
    return -1;
}

2.4 性能分析

当字符匹配失败时，结束本轮匹配，然后模式串向右移动一个字符的距离并开启下一轮匹配。

假设 n 表示文本串的长度，m 表示模式串的长度，那么模式串最多和文本串比较 n - m + 1 轮。

下图模式串中被碧绿色覆盖的区域表示已成功匹配的字符，被红色覆盖的区域表示匹配失败的字符，未被任何颜色覆盖的区域表示尚未进行匹配的字符。

最理想情况下，只需一轮比较就能完全匹配成功，一共比较 m 次字符。

这种情况下的时间复杂度为 $O(m)$ 。

而在最坏情况下，一共比较了 n - m + 1 轮都没有完全匹配成功，并且每一轮都比较至模式串的末位字符才失败。

这种情况下的时间复杂度为 $O(m \times (n - m + 1))$ ，而 m 又通常远小于 n，因此最终时间复杂度可表示为 $O(nm)$ 。

当参与比较的字符集所包含的字符越多时，最坏情况出现的概率将越低。当字符集所包含的字符越多时，就更容易在每轮比较开始时失败，而不会等到比较至模式串的末位字符时才失败，也就更不容易出现最坏情况。

3. KMP

3.1 算法简介

KMP 是 Knuth-Morris-Pratt 的简称（取名自 3 位发明人的名字，即：Donald Knuth、James Hiram Morris、Vaughan Pratt，因此人们也称它为克努特—莫里斯—普拉特操作），是一种改进的字符串匹配算法。

KMP 算法与蛮力算法的对比

在先前的蛮力算法中，每当字符匹配失败时，模式串就会向右移动一个字符，然后再与字符串中的字符依次进行匹配，在这个过程中，可能存在一些没有必要的比较。

与蛮力算法相比，KMP 算法充分利用了先前比较过的内容，可以“很聪明地”跳过一些不必要的比较位置。

那 KMP 算法是怎么跳过这些不必要的比较内容呢？

3.2 next 表的使用

KMP 算法会预先根据 模式串 的内容生成一张 next 表（一般是一个数组）。

以模式串“ABCDABCE”为例，生成的 next 表如下图：

暂时不管 next 表是怎么生成的，先看看怎么使用 next 表。

与蛮力算法的实现方式一一样，需要引入 pi 和 ti 两个变量：

用 pi 表示模式串中正在进行比较的字符的索引，它的取值范围是 $pi \in [0, plen)$ 。
用 ti 表示文本串中正在进行比较的字符的索引，它的取值范围是 $ti \in [0, tlen)$ 。

比较方式也一样：当 pi 与 ti 指向的字符匹配成功时，pi 与 ti 分别自增一，即：pi++; ti++;。

但当 pi 与 ti 指向的字符匹配失败时，即失配时，KMP 算法的做法是：将 next[pi] 的值赋值给 pi，也就是直接让模式串向右移动 pi - next[pi] 个字符。

比如：

再比如：

3.3 核心原理

当 d、e 失配时，如果希望模式串 Pattern 能够一次性向右移动一大段距离，然后直接比较 d、c 字符的前提是：子串 A 必须等于子串 B。

所以 KMP 必须在失配字符 e 左边的子串中找出符合条件的子串 A、B，从而得知向右移动的距离。

由上图可知，向右移动的距离为：字符 e 左边子串的长度 - 子串 A 的长度，这又等价于字符 e 的索引 - 字符 c 的索引。

根据 KMP 中对 next 表的设想，字符 c 的索引 等价于 next[字符 e 的索引]，所以向右移动的距离为：e 的索引 - next[e 的索引]。

总结

如果在 pi 位置失配，向右移动的距离是 pi - next[pi]。当 next[pi] 越小时，移动距离越大。
next[pi] 是 pi 左边子串的 真前缀后缀 的 最大公共子串 长度。

真前缀后缀的最大公共子串长度

对于给定字符串 Str 的真前缀和真后缀都不包含原字符串本身。

对于模式串 ABCDABCE 来说，其本身与其子串的真前缀、真后缀的最大公共子串长度如下表：

最终可以得到如下总结表：

以字符串 ABCDABCE 为例，其真前缀、真后缀的最大公共子串长度是 0；

以字符串 ABCDABC 为例，其真前缀、真后缀的最大公共子串长度是 3；

以字符串 ABCDAB 为例，其真前缀、真后缀的最大公共子串长度是 2；

这个总结表并不是最终的 next 表，将总结表中“最大公共子串长度”行中的所有数据向后移动 1 位，并将首字符设置为 -1 即可得到 next 表。

那为什么要向后移动 1 位呢？

以模式串 ABCDABCE 为例，当字符 E 失配时，需要用到字符串 ABCDABC 中真前缀、真后缀的最大公共子串长度；再比如当 C 失配时，需要用到字符串 ABCDAB 中真前缀、真后缀的最大公共子串长度。

那为什么 next 表中索引 0 位置的元素是 -1 呢？

KMP 算法可以看成是在蛮力算法实现方式一上进行的改进。

如果要用到 next[0] 的值，就表示模式串中第一个字符与字符串中的字符匹配失败，然后需要再次使用模式串中的第一个字符与字符串中的下一个字符进行比较，即：ti++; pi = 0;。

在 KMP 算法中，当出现失配时，需要使模式串一次性向右移动一大段距离，体现在代码层面就是 pi = next[pi];。

如果是在模式串的首位字符出现失配，那么 pi = next[0] = -1，如果此时执行 ti++; pi++; 那么恰好等价于 ti++; pi = 0;。

因此可以初步得出 KMP 算法的实现：

/**
 * @author mofan
 * @date 2022/12/15 20:50
 */
public class KMP {
    public static int indexOf(String text, String pattern) {
        if (text == null || pattern == null) return -1;
        char[] textChars = text.toCharArray();
        int tlen = textChars.length;
        if (tlen == 0) return -1;
        char[] patternChars = pattern.toCharArray();
        int plen = patternChars.length;
        if (plen == 0 || plen > tlen) return -1;

        // 构建 next 表
        int[] next = next(pattern);

        int pi = 0, ti = 0, lenDelta = tlen - plen;
        while (pi < plen && ti - pi <= lenDelta) {
            // 模式串索引 0 位置的字符失配或两个字符匹配成功
            if (pi < 0 || patternChars[pi] == textChars[ti]) {
                ti++;
                pi++;
            } else {
                // 失配时使用 next 表
                pi = next[pi];
            }
        }
        return pi == plen ? ti - pi : -1;
    }

    private static int[] next(String pattern) {
        // todo next() 还有待实现
        return null;
    }
}

为什么是“最大”公共子串长度？

假设文本串是 AAAAABCDEF，模式串是 AAAAB。

模式串的子串的真前缀、真后缀的最大公共子串长度如下表：

当模式串与字符串的字符比较发生失配时，应该将 1、2、3 中的哪个值赋值给 pi 才是正确的呢？

假设将 3 赋值给 pi，即模式串相比于字符串向右移动了一个字符单位，之后再进行比较，最终匹配成功。

如果是将 1 赋值给 pi，即模式串相比于字符串向右移动了三个字符单位，之后再进行比较时会错过成功匹配的机会。

公共子串的长度越小，模式串相比于字符串向右移动的距离越大，就越不安全；公共子串的长度越大，模式串相比于字符串向右移动的距离越小，就越安全；

3.4 next 表的构建思路

首先明白 next 数组中的元素表示什么意思？

以 next[m] 为例，它表示模式串中索引 m 指向的字符的左边子串的真前缀、真后缀的最大公共子串长度（或许有点绕，多读几遍试着理解，这一定要理解并牢记，不然后面的内容更难理解 😜）。

下图表示一个抽象的模式串，可以看到索引 [0, n) 形成的子串与索引 n 和索引 i 之间的一个子串的颜色组成相同，可以认为这两个子串相等：

现有已知条件 next[i] == n：

① 如果 Pattern[i] == Pattern[n]，即模式串中索引 n 和索引 i 指向的字符相等，那么 next[i + 1] = n + 1。

② 那如果 Pattern[i] != Pattern[n] 呢？

在模式串 [0, n) 的索引区间内存在一个 k，且有 next[n] == k。

如果 Pattern[i] == Pattern[k]，那么有 next[i + 1] = k + 1。

那如果 Pattern[i] != Pattern[k] 呢？

将 k 带入 n，重复执行 ②。

再次梳理

首先得明白 next 数组表示什么？

以 next[i] = n 为例，它表示 模式串中索引 i 指向的字符的左边子串 的真前缀、真后缀的最大公共子串长度为 n。以 iStr 表示模式串中索引 i 指向的字符的左边子串，此时 iStr 的长度可以表示为：

n + X + n

X 表示 iStr 的中间剩余子串。

假设在 next 数组中，已知 next[i] = n，在实际编码时，使用 next[0] = -1 作为已知值，现在需要求取 next[i + 1] 的值。以 chars 表示模式串对应的字符数组。

要求 next[i + 1] 的值，相当于要求模式串中索引范围为 [0, i] 组成的子串的真前缀、真后缀的最大公共子串长度。已知的 next[i] = n 表示模式串中索引范围为 [0, i - 1] 组成的子串的真前缀、真后缀的最大公共子串长度为 n，这可以推导出模式串中索引范围为 [0, n - 1] 组成的子串即为模式串中索引范围为 [0, i - 1] 组成的子串的符合条件的真前缀（有点绕，需要理清楚）。

在求取 next[i + 1] 的值时，如果 chars[n] == chars[i]，那么 next[i + 1] 的值等于在 next[i] 的基础上加一，即 next[i + 1] = next[i] + 1 = n + 1。

当 chars[n] != chars[i] 时，需要在原本的真前缀、真后缀最大公共子串的范围上进行缩小，相当于缩小 n。对真前缀来说，范围向左缩小；对真后缀来说，范围向右缩小。由于 next[i] = n，那么模式串中索引范围为 [0, i - 1] 组成的子串的长度可以表示为 n + X + n。

假设 next[n] = k，这表示 next[i] 对应的最大公共子串的真前缀子串的真前缀、真后缀的最大公共子串长度为 k（有点绕，需要理清楚），那么模式串中索引范围为 [0, i - 1] 组成的子串的长度又可以表示为：

1	n + X + n = k + m + k + X + k + m + k

相当于 n = k + m + k，此时需要判断 chars[i] 与 chars[k] 是否相等，相等情况下，next[i + 1] = k + 1，否则继续前文类似操作，直到求出 next[i + 1]。

那 next[n] = k 代表着什么？

在代码实现中，这代表将 next[n] 赋值给原本已知的 n，以修改 n 的值。因为 n 表示在计算 next[i + 1] 过程中与 chars[i] 进行比较的字符索引，还表示 当前符合条件 的真前缀长度。

next[i] = n 是已知量，i 一定大于 n，next 数组的计算是按索引增加的，因此 next[n] 一定是已知值，无需担心。

next() 方法的实现

private static int[] next(String pattern) {
    char[] chars = pattern.toCharArray();
    int[] next = new int[chars.length];

    next[0] = -1;
    int i = 0, n = -1, iMax = chars.length - 1;
    while (i < iMax) {
        if (n < 0 || chars[i] == chars[n]) {
            next[++i] = ++n;
        } else {
            n = next[n];
        }
    }
    return next;
}

3.5 next 表的不足之处

假设文本串是 AAABAAAAB，模式串是 AAAAB，那么模式串的 next 表和比较过程如下：

在这种情况下，KMP 算法显得比较笨拙，退化成了蛮力算法。

3.6 next 表的优化思路

已知 next[i] == n, next[n] == k：

如果 Pattern[i] != d，即模式串中索引位置 i 指向的字符与字符串中的字符 d 匹配失败，就让模式串滑动到 next[i]（即模式串中索引位置 n）位置与字符 d 再进行比较；

如果 Pattern[n] != d，即模式串中索引位置 n 指向的字符与字符串中的字符 d 匹配失败，就让模式串滑动到 next[n]（即模式串中索引位置 k）位置与字符 d 再进行比较；

如果 Pattern[i] == Pattern[n]，那么当 i 位置指向的字符失配时，模式串最终必然会滑动到 k 位置再与字符 d 进行比较。

所以 next 表中的 next[i] 可以直接存储 next[n]（也就是 k）的值。

优化后的代码实现

private static int[] next(String pattern) {
    char[] chars = pattern.toCharArray();
    int[] next = new int[chars.length];

    next[0] = -1;
    int i = 0, n = -1, iMax = chars.length - 1;
    while (i < iMax) {
        if (n < 0 || chars[i] == chars[n]) {
            ++i;
            ++n;

            if (chars[i] == chars[n]) {
                next[i] = next[n];
            } else {
                next[i] = n;
            }
        } else {
            n = next[n];
        }
    }
    return next;
}

next 表的优化效果

还是以文本串 AAABAAAAB，模式串 AAAAB 为例，经过优化后的 next 表和比较过程如下：

可以很直观地看到，next 表经过优化后，那些没有必要的比较过程已经不存在了。

3.7 性能分析

KMP 算法主逻辑：

最好时间复杂度： $O(m)$ ， $m$ 指模式串的长度
最坏时间复杂度： $O(n)$ ，不会超过 $O(2n)$ ， $n$ 指字符串的长度

next 表的构造过程跟 KMP 算法主逻辑类似，时间复杂度为 $O(m)$ 。

因此 KMP 算法整体：

最好时间复杂度： $O(m)$
最坏时间复杂度： $O(n + m)$
空间复杂度： $O(m)$

蛮力算法为什么低效？

当字符失配时，蛮力算法：

ti 回溯到左边位置
pi 回溯到 0

而 KMP 算法：

ti 不必回溯
pi 不一定回溯到 0

3.8 【补充】另一种实现

KMP 的核心是 next 数组的计算，以 next[i] 为例，在上文的实现中，这表示模式串中索引为 i 的字符的 左边子串 （即模式串中索引范围为 [0, i - 1] 的子串）的真前缀、真后缀的最长公共子串长度。在其他资料中会出现 next[i] 表示模式串中索引范围为 [0, i] 的子串的真前缀、真后缀的最长公共子串长度的情况，那这样的 next 数组怎么实现呢？

将上文对 next 数组的实现称为“原实现”，本节探讨的 next 数组的实现称为“新实现”。

原实现与新实现相比，相当于是将新实现中得到的 next 数组整体向右移动一位、并将首位设置为 -1 而得到的。

新实现与原实现的实现思路类似，首先也需要设置 next 数组的初始值，令 next[0] = 0，这不难理解，单个字符的真前缀、真后缀的最长公共子串长度肯定为 0。

第一个待计算的模式串索引为 1，因此 i 的初始值为 1；n 表示当前符合条件的真前缀长度，因此 n 的初始值与 i 的初始值一样，都是 1。

新实现的逻辑与原实现基本一致，只不过：

当模式串中索引 i 与索引 n 指向的字符不相等、并且 n 已经等于 0 时，这表示模式串中索引范围为 [0, i] 的子串的真前缀、真后缀的最长公共子串长度为 0，因此将 0 赋值给 next[i]，赋值完成后需要将 i 向前移动一位以便进行下一位的计算；
原实现中 n 被赋值为 next[n]，原实现相比于新实现，是新实现整体向右移动一位得到的结果，因此在新实现中的 n 被赋值为 next[n - 1]。

public int[] next(String s) {
    char[] chars = s.toCharArray();
    int[] next = new int[chars.length];

    next[0] = 0;
    int i = 1, n = 0, iMax = chars.length - 1;
    while (i <= iMax) {
        if (chars[i] == chars[n]) {
            next[i++] = ++n;
        } else {
            if (n == 0) {
                next[i++] = 0;
            } else {
                n = next[n - 1];
            }
        }
    }
    return next;
}

尝试使用新实现完成 KMP，其逻辑与原实现也类似。只不过当两个字符匹配失败：

并且 pi 等于 0 时，这表示文本串参与比较的字符与模式串中的第一个字符就不匹配，需要使用文本串中的下一个字符继续与模式串中的第一个字符进行比较。
如果 pi 不等于 0，则按照计算出的 next 数组对 pi 进行重新赋值，此时赋的值应该是 next[pi - 1]，而不是 next[pi]，因为原实现的 next 数组是相当于将新实现的 next 数组整体向右移动一位、并将首位设置为 -1 得到的。

public static int indexOf(String text, String pattern) {
    if (text == null || pattern == null) return -1;
    char[] textChars = text.toCharArray();
    int tlen = textChars.length;
    if (tlen == 0) return -1;
    char[] patternChars = pattern.toCharArray();
    int plen = patternChars.length;
    if (plen == 0 || plen > tlen) return -1;

    // 构建 next 表
    int[] next = next(pattern);

    int ti = 0, pi = 0, lenDelta = textChars.length - plen;
    while (pi < plen && ti - pi <= lenDelta) {
        if (patternChars[pi] == textChars[ti]) {
            ti++;
            pi++;
        } else {
            if (pi == 0) {
                ti++;
            } else {
                pi = next[pi - 1];
            }
        }
    }
    return pi == plen ? ti - pi : -1;
}