力扣题目：Find the Index of the First Occurrence in a String

给定原串 s 长度为 n，模式串 p 长度为 m。

先给个暴力解法：

int fun(String s, String t) {
    int n = s.length(), m = t.length();
    for (int idx = 0; idx <= n - m; idx++) {
        int i = idx, j = 0;
        for ( ; j < m; ++i, ++j) {
            if (s.charAt(i) != t.charAt(j)) break;
        }
        if (j == m) return idx;
    }
    return -1;
}

首先，KMP（Knuth–Morris–Pratt algorithm）和暴力解法的不同之处是，当遇到不相同的字符时，暴力解法采取的措施是：原串指针回到本次开始位置的下一个位置，模式串指针回到第一个位置。而 KMP 采取的措施是：原串指针保持不动，模式串指针回到已匹配模式串的相同前缀的下一个位置。

  1. 为什么当遇到原串和模式串不匹配时，需要回到已匹配的模式串的「相同前缀」的下一个位置？

相同前缀指的是，如果一个字符串中包含相同的前缀和后缀，比如 aabbaa 包含相同的前缀和后缀，都为 aa，那么叫这个前缀为相同前缀（我自己起的名）。

如果已匹配模式串中存在相同前缀和后缀，并且后缀的最后一个字符和原串未匹配位置字符相同，这时只需要从相同前缀的下一个位置开始和原串不匹配字符处继续往下比较即可。如果模式串中不存在相同的前缀和后缀，那就只能从模式串的第一个字符开始，继续往下和原串进行比较。

举例子：原串 acbacc，模式串 acbacb，如果现在该比较的是第 6 个字符，发现不相同（c != b），此时应该检查模式串不匹配位置前一个字符是什么（模式串第 5 个字符是 c），发现和原串不匹配字符 c 相同，那么下一轮开始比较的位置应该是：原串第 6 个字符，模式串第 3 个字符。

如果我们事先不知道已匹配模式串中的相同的前、后缀的位置，那么每当遇到原串和模式串不匹配的时候，我们都要重新扫描一遍模式串的已匹配部分，看是否存在相同的前、后缀，并据此判断模式串下次匹配开始的位置，这个不断扫描查找相同前、后缀过程的时间复杂度是 O(m^2) 的，总体复杂度是 O(n * m^2)，这显然比暴力解法 O(n * m) 更慢。那怎么处理呢？

  1. next 数组是干嘛用的？是怎么生成的？是怎么使用的？

可以考虑用空间换时间，预先将模式串中每个位置如果不匹配，下次应该跳转的位置给记录下来，放到 next 数组中，那么在遇到不匹配的情况，就可以直接在 next 数组中很快的找出模式串下次匹配应该开始的位置。 那么 next 数组应该怎么生成呢？

生成 next 的具体步骤：

  • 初始化：int[] next = new int[m]; int j = 0, i = 1;
  • 如果匹配（p[j] == p[i]）：next[i] = j + 1; ++i; ++j;
  • 如果不匹配（p[j] ！= p[i]）：令 j = next[j - 1]，之后如果匹配，则返回上个步骤；如果不匹配，继续令 j = next[j - 1]，直到 j == 0，此时将 next[i] = j。虽然这里有使用 while 循环，但是时间复杂度应该并不是 O(m)的。

下面是生成 next 数组的完整代码。其中代码的逻辑和上述步骤相同，但是将上述步骤进行了一些合并，具体请见代码。

int[] next = new int[m];
for (int i = 1, j = 0; i < m; ++i) {
    while (j > 0 && p[i] != p[j]) j = next[j - 1];
    if (p[i] == p[j]) ++j;
    next[i] = j;
}

现在有了 next 数组，可以方便的查找模式串中当前字符的下一个开始匹配位置了，那么该怎么使用呢？

在原串中使用指针 i，在模式串中使用指针 j。

  • 初始化：int i = 0, j = 0;
  • 如果匹配（s[i] == p[j]）：++i; ++j; 如果 j == m，说明整个模式串匹配成功，直接返回 i - m + 1。
  • 如果不匹配（s[i] != p[j]）：令 j = next[j - 1]，之后如果匹配，则返回上个步骤；如果不匹配，继续令 j = next[j - 1]，直到 j == 0，说明整个已经匹配过的模式串中不存在相同的前、后缀。

代码：

for (int i = 0, j = 0; i < n; ++i) {
    while (j > 0 && s[i] != p[j]) j = next[j - 1];
    if (s[i] == p[j]) ++j;
    if (j == m) return i - m + 1;
}

下面是整个 KMP 的完整代码：

public int KMP(String ss, String pp) {
    char[] s = ss.toCharArray();
    char[] p = pp.toCharArray();
    int n = s.length, m = p.length;
    if (m == 0) return 0;
    int[] next = new int[m];
    for (int j = 0, i = 1; i < m; ++i) {
        while (j > 0 && 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 > 0 && s[i] != p[j]) j = next[j - 1];
        if (s[i] == p[j]) ++j;
        if (j == m) return i - m + 1;
    }
    return -1;
}
public int KMP(String ss, String pp) {
    if (pp.isEmpty()) return 0;
    int n = ss.length(), m = pp.length();
    char[] s = (" " + ss).toCharArray();
    char[] p = (" " + pp).toCharArray();
    int[] next = new int[m + 1];
    for (int i = 2, j = 0; i <= m; ++i) {
        while (j > 0 && p[i] != p[j + 1]) j = next[j];
        if (p[i] == p[j + 1]) ++j;
        next[i] = j;
    }

    for (int i = 1, j = 0; i <= n; ++i) {
        while (j > 0 && s[i] != p[j + 1]) j = next[j];
        if (s[i] == p[j + 1]) ++j;
        if (j == m) return i - m;
    }
    return -1;
}

希望该篇文章对你有帮助：）

参考文章：【宫水三叶】简单题学 KMP 算法