KMP算法

KMP 算法 是一个模式匹配算法。对应的Brute-Force（简称BF算法）是暴力匹配，也叫朴素匹配。BF效率很低。所以常用KMP 算法类进行字符串的模式匹配

原理

整体套用宫水三叶的题解

https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/solution/shua-chuan-lc-shuang-bai-po-su-jie-fa-km-tb86/

KMP 算法的重点是构造 next 数组。其次是使用 next 数组，KMP算法的原理其实很简单。

1. 匹配过程

在模拟 KMP 匹配过程之前，我们先建立两个概念：

• 前缀：对于字符串 abcxxxxefg，我们称 abc 属于 abcxxxxefg 的某个前缀。
• 后缀：对于字符串 abcxxxxefg，我们称 efg 属于 abcxxxxefg 的某个后缀。

然后我们假设原串为 abeababeabf，匹配串为 abeabf：

我们可以先看看如果不使用 KMP，会如何进行匹配（不使用 substring 函数的情况下）。

首先在「原串」和「匹配串」分别各自有一个指针指向当前匹配的位置。

首次匹配的「发起点」是第一个字符 a。显然，后面的 abeab 都是匹配的，两个指针会同时往右移动（黑标）。

在都能匹配上 abeab 的部分，「朴素匹配」和「KMP」并无不同。

直到出现第一个不同的位置（红标）：

接下来，正是「朴素匹配」和「KMP」出现不同的地方：

先看下「朴素匹配」逻辑：

1. 将原串的指针移动至本次「发起点」的下一个位置（b 字符处）；匹配串的指针移动至起始位置。

2. 尝试匹配，发现对不上，原串的指针会一直往后移动，直到能够与匹配串对上位置。

如图：

也就是说，对于「朴素匹配」而言，一旦匹配失败，将会将原串指针调整至下一个「发起点」，匹配串的指针调整至起始位置，然后重新尝试匹配。

这也就不难理解为什么「朴素匹配」的复杂度是 $O(m * n)$ 了。

然后我们再看看「KMP 匹配」过程：
首先匹配串会检查之前已经匹配成功的部分中里是否存在相同的「前缀」和「后缀」。如果存在，则跳转到「前缀」的下一个位置继续往下匹配：

跳转到下一匹配位置后，尝试匹配，发现两个指针的字符对不上，并且此时匹配串指针前面不存在相同的「前缀」和「后缀」，这时候只能回到匹配串的起始位置重新开始：

到这里，你应该清楚 KMP 为什么相比于朴素解法更快：

因为 KMP 利用已匹配部分中相同的「前缀」和「后缀」来加速下一次的匹配。

因为 KMP 的原串指针不会进行回溯（没有朴素匹配中回到下一个「发起点」的过程）。

第一点很直观，也很好理解。

我们可以把重点放在第二点上，原串不回溯至「发起点」意味着什么？

其实是意味着：随着匹配过程的进行，原串指针的不断右移，我们本质上是在不断地在否决一些「不可能」的方案。

当我们的原串指针从 $i$ 位置后移到 $j$ 位置，不仅仅代表着「原串」下标范围为 $[i,j)$ 的字符与「匹配串」匹配或者不匹配，更是在否决那些以「原串」下标范围为 $[i,j)$ 为「匹配发起点」的子集。

2. 分析实现

到这里，就结束了吗？要开始动手实现上述匹配过程了吗？

我们可以先分析一下复杂度。如果严格按照上述解法的话，最坏情况下我们需要扫描整个原串，复杂度为 $O(n)$。同时在每一次匹配失败时，去检查已匹配部分的相同「前缀」和「后缀」，跳转到相应的位置，如果不匹配则再检查前面部分是否有相同「前缀」和「后缀」，再跳转到相应的位置 … 这部分的复杂度是 ，$O(m^2)$因此整体的复杂度是 $O(n m^2)$，而我们的朴素解法是 $O(m n)$ 的。

说明还有一些性质我们没有利用到。

显然，扫描完整原串操作这一操作是不可避免的，我们可以优化的只能是「检查已匹配部分的相同前缀和后缀」这一过程。

再进一步，我们检查「前缀」和「后缀」的目的其实是「为了确定匹配串中的下一段开始匹配的位置」。

同时我们发现，对于匹配串的任意一个位置而言，由该位置发起的下一个匹配点位置其实与原串无关。

举个例子，对于匹配串 abcabd 的字符 d 而言，由它发起的下一个匹配点跳转必然是字符 c 的位置。因为字符 d 位置的相同「前缀」和「后缀」字符 ab 的下一位置就是字符 c。

可见从匹配串某个位置跳转下一个匹配位置这一过程是与原串无关的，我们将这一过程称为找 next 点。

显然我们可以预处理出 next 数组，数组中每个位置的值就是该下标应该跳转的目标位置（ next 点）。

当我们进行了这一步优化之后，复杂度是多少呢？

预处理 next 数组的复杂度未知，匹配过程最多扫描完整个原串，复杂度为 $O(n)$。

因此如果我们希望整个 KMP 过程是 $O(m + n)$ 的话，那么我们需要在 $O(m)$ 的复杂度内预处理出 next 数组。

所以我们的重点在于如何在 $O(m)$ 复杂度内处理处 next 数组。

3. next 数组的构建 （重点）

接下来，我们看看 next 数组是如何在 $O(m)$ 的复杂度内被预处理出来的。

假设有匹配串 aaabbab，我们来看看对应的 next 是如何被构建出来的。

实际上写代码时需要：j = 0, i = i。有些代码模板也是：j = -1,i = 0，反正要满足 j < i一般也是i = j + 1

if(p[j] == p[i]){
    j++;i++;			// 先 ++ ，再存储next[i] (next[0] = 0。提前默认设置)
    next[i] = j + 1;
}

如果两个字符不相同，就需要回退。回退方式就是 j = next[j - 1]

回退到最后就是 j == 0 ，如果退到 j == 0 了，那么 j 就不回退了，但是 i 继续自增，直到又可以继续增加 j 。这个 j 的判断和 j 的初始值有关，j 初始为 0 ，就是 j == 0 , j 初始为 -1 ，就是 j == -1。循环条件看习惯写，反正就是到了初始值就不能再退了。

这就是整个 next 数组的构建过程，时空复杂度均为 $O(m)$。

至此整个 KMP 匹配过程复杂度是 $O(m + n)$ 的。

构造 next 数组代码：

下面的代码出自数据结构教程：

void getNext(SqString t, int next[]) {				// next[] 的大小等于 t.length + 1
    int i = 0,j = -1;
    next[0] = -1;
    while(i < t.length - 1) {
        if(j == -1 || t.data[i] == t.data[j]) {
            i++;j++;
            next[i] = j;
        } else j = next[j];							// 回退
    }
}

我常用的构造思路：

void getNext(SqString t, int next[]) {				// next[] 的大小等于 t.length
    next[0] = 0;									
    for (int i = 1, j = 0; i < t.length; i++) {
        while (j > 0 && t.data[i] != t.data[j]) {
            j = next[j - 1];
        }
        if (t.data[i] == t.data[j]) {
            j++;
        }
        next[i] = j;
    }
}

注意：

int next[t.length]; 方式声明 next[0] 默认等于 -1

vector<int> next[t.length]; 方式声明 next[0] 默认等于 0

为了不出错可以提前就显式赋值。

使用 next 数组进行模式匹配

这里的代码时基于上面第二种构造思路实现的。

需要的结果时如果子串于原串匹配了，返回起始位置再原串中的下标

for(int i = 0, j = 0; i < n; ++i) {
    // 下面两行是匹配的代码
    while(j > 0 && t.data[i] != t.data[j]) j = next[j - 1];
    if(t.data[i] == t.data[j]) j++;
    
    // 下面一行代码可能会根据题目要求做出改变
    if(j == t.length) return i - m + 1;
}

可以发现代码和构造 next 数组很像。区别就是构造时 i = 1, j = 0 ， 匹配时 i = 0 , j = 0 ； 构造时需要每一步给next数组赋值，匹配时就不需要赋值操作了，if(j == t.length) return i - m + 1;是根据题目要求会变化的。

4. 代码实现（题解）

原题链接 ： 28. 找出字符串中第一个匹配项的下标

整个过程与上述分析完全一致，一些相关的注释我已经写到代码里。

代码：

java：

class Solution {
    // KMP 算法
    // ss: 原串(string)  pp: 匹配串(pattern)
    public int strStr(String ss, String pp) {
        if (pp.isEmpty()) return 0;
        
        // 分别读取原串和匹配串的长度
        int n = ss.length(), m = pp.length();

        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        // 构建 next 数组，数组长度为匹配串的长度（next 数组是和匹配串相关的）
        int[] next = new int[m];
        // 构造过程
        for (int i = 1, j = 0; i < m; i++) {
            // 匹配不成功的话，j = next(j)
            while (j > 0 && p[i] != p[j + 1]) j = next[j - 1];
            // 匹配成功的话，先让 j++
            if (p[i] == p[j]) j++;
            // 更新 next[i]，结束本次循环，i++
            next[i] = j;
        }

        // 匹配过程，i = 0，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】
        for (int i = 0, j = 0; i < n; i++) {
            // 匹配不成功 j = next(j)
            while (j > 0 && s[i] != p[j]) j = next[j - 1];
            // 匹配成功的话，先让 j++，结束本次循环后 i++
            if (s[i] == p[j]) j++;
            // 整一段匹配成功，直接返回下标
            if (j == m) return i - m + 1;
        }

        return -1;
    }
}

C++：

class Solution {
public:
    int strStr(string s, string p) {
        int n = s.size(), m = p.size();
        if(m == 0) return 0;
        vector<int> next(m);
        //预处理next数组
        for(int i = 1, j = 0; i < m; i++){
            while(j and p[i] != p[j]) j = next[j - 1];
            if(p[i] == p[j]) j++;
            next[i] = j;
        }
        //匹配过程
        for(int i = 0, j = 0; i < n; i++){
            while(j and s[i] != p[j]) j = next[j - 1];
            if(s[i] == p[j]) j++;
            if(j == m) return i - m + 1;
        }
        return -1;
    }
};