【写在后面】

“Java算法系列”目录如下（更新ing）：

  • 数据结构相干算法
  • 八大排序算法：冒泡排序、抉择排序、插入排序、希尔排序、疾速排序、归并排序、基数排序、堆排序
  • 四大查找算法：线性查找、二分查找、插值查找、斐波那契查找
  • 九大罕用算法：分治算法、动静布局算法、KMP算法、贪婪算法、Prim算法、Kruskal算法、Dijkstra算法、Floyd算法、骑士环游回溯算法

本篇为九大罕用算法之KMP算法。

〇、根本介绍

Knuth-Morris-Pratt算法，简称为 “KMP算法”，是一个字符串查找算法。

咱们当初面临这样一个问题：

有一个文本串T，和一个模式串P，当初要查找P在T中的地位，怎么查找呢？

本例可参考：NC149 KMP算法

对于这样的字符串模式匹配问题，除了KMP算法之外，还有不少算法。这几个算法的性能从上到下顺次递增：

  • 暴力匹配算法（Brute-Force）
  • KMP算法
  • Horspool算法
  • Boyer-Moore算法
  • Sunday算法
  • RK算法

KMP算法是一个十分经典的算法。但相比之下，其余算法可能来得更简略而高效。至于咱们为什么只学KMP呢？我也不晓得（笑）。

一、字符串暴力匹配算法

字符串匹配问题就是在主串（text，咱们称之为T）中定位模式串（pattern，咱们称之为P）的问题。

在开始学习KMP算法之前，请先学习暴力匹配算法。该算法非常简单也十分易于了解，请您不要跳过，因为KMP算法就是在以下代码的根底上进行批改的：

/** * 字符串匹配的暴力匹配算法（Brute-Force） * * @param T 主串（text） * @param P 模式串（pattern） * @return 模式串在主串中呈现的地位，如未呈现则返回-1 */public static int BruteForce(String T, String P) {    char[] t = T.toCharArray();    char[] p = P.toCharArray();    int i = 0; // 主串的地位指针    int j = 0; // 模式串的地位指针    while (i < t.length && j < p.length) {        if (t[i] == p[j]) { // 若匹配，i、j指针后移            i++;            j++;        } else {            i = i - j + 1; // 若不匹配，i回退，j置0            j = 0;        }    }    if (j == p.length) // 匹配胜利        return i - j;    else // 匹配失败        return -1;}

在主串 ABCEABCDAB 中匹配模式串 ABCD 的图解如下：

二、求next数组（手算）

从暴力匹配算法能够看出，若产生不匹配（即t[i] != p[j]）时，i 总是要进行回退。

可是，i 肯定要回退吗？

比方下面的例子，咱们曾经晓得模式串中不存在反复的字符，又晓得主串的前三位（T[0~2]）和模式串的前三位（P[0~2]）是匹配的，那么咱们就能够晓得主串的前三位不存在第二个模式串的首字母"A"，因而就不须要回退 i 了。

所以，咱们能不能利用模式串的“曾经局部匹配的字符”这个无效信息，放弃 i 指针不回退、并将 j 指针移到适合的地位呢？

因而咱们定义了一个辅助数组next。咱们能够应用一个数组next保留指针 j 应该回退的地位。

对于同一个字符串，网上常见的next数组有两种，一种是next[0] = -1，一种是next[0] = 0。KMP的原始论文中应用的是next[0] = 0，但上面我会使得next[0] = -1。这两种next数组的区别仅仅在于后者的每一项的值会比前者大1，其逻辑是一样的。

咱们先把握两个概念：前缀和后缀。

以字符串"bread"为例：

  • 前缀："b"，"br"，"bre"，"brea"
  • 后缀："d"，"ad"，"ead"，"read"

再把握一个概念：前缀后缀公共元素的长度（以下简称为“局部匹配值”）。

如字符串"ABCD"的前缀后缀没有公共元素，因而局部匹配值为0；字符串"ABCDA"的前缀后缀公共元素为"A"，因而局部匹配值为1；字符串"ABCDAB"的前缀后缀公共元素为"AB"，因而局部匹配值为2。

当初给定一个模式串"ABCDABD"，求出其各个子串的局部匹配值：

咱们为什么要失去一个模式串的前缀后缀公共元素的长度表（局部匹配表）呢？这个表有什么用？接下来看以下模式串"ABCDABD"的字符串匹配的例子：

发现了吗？指针 j 应该回退的地位就等于 j 位前的子串的前缀后缀公共元素的长度。

因而，对于模式串"ABCDABD"，初始化next[0] = -1，咱们能够失去其next数组：

当然，网上也存在另一种初始化next[0] = 0的next数组，就是下面数组的值加1：

三、求next数组（编写代码）

那么，如何编写代码来求next数组呢？

咱们设置一个前缀指针 k 和后缀指针 j，初始化k = -1, j = 0。

对于前缀指针，有两种状况：

  • 前缀指针为初始化值-1。

    • 此时局部匹配值为0。将前缀指针 k 与后缀指针 j 各后移，使得前缀指针指向第0位，后缀指针指向下一位，将局部匹配值0赋给next数组：

      if (k == -1) {    k++; // k = 0，k的值即为局部匹配值    j++; // 第j位的局部匹配值应填在next表的j+1位    next[j] = k;}

  • 前缀指针不为初始化值-1。比拟前缀指针的值P[k] 与后缀指针的值 P[j]，有两种状况：

    • P[k] == P[j]。此时局部匹配值为 k+1。将前缀指针 k 与后缀指针 j 各后移，使得后缀指针指向下一位，将局部匹配值（即此时前缀指针的值k）赋给next数组：

      else if (p[j] == p[k]) {    k++; // k自增后，k的值即为局部匹配值    j++; // 第j位的局部匹配值应填在next表的j+1位    next[j] = k;}

    • P[k] != P[j]。看上面一个例子：

      看第三步，当咱们判断完前缀XYXY与后缀XYXY雷同后，却判断出前缀的下一位Y与后缀的下一位X不相等，此时咱们应该再向左挪动前缀指针，直至前缀指针回到初始值-1或呈现p[j] == p[k]能力更新next数组。

      那么怎么挪动呢？咱们心愿用前缀XYXY的前缀去匹配后缀XYXY的后缀，等价于在前缀XYXY中进行前缀和后缀的匹配。

      咱们晓得，next[k]的含意是：前k-1位形成的字符串的前缀后缀公共元素的长度，也即此公共元素前缀的下一位的下标值。

      因而，令k = next[k]后，此时k指向的是已匹配的前缀的下一位，此时j仍指向已匹配的后缀的下一位。这时就能够持续比拟前缀指针的值P[k] 与后缀指针的值 P[j]了，直至前缀指针回到初始值-1或呈现p[j] == p[k]，更新next数组。

综上，能够写出求next数组的代码：

public static int[] getNext(String ps) {    char[] p = ps.toCharArray();    int[] next = new int[p.length];    next[0] = -1;    int j = 0;    int k = -1;    while (j < p.length - 1) {        if (k == -1 || p[j] == p[k]) {            k++;            j++;            next[j] = k;        } else {            k = next[k];        }    }    return next;}

四、KMP算法

咱们晓得，next数组即保留了指针 j 应该回退的地位。因而能够在暴力匹配算法的根底上进行简略的批改，即可失去KMP算法：

/** * 字符串匹配的KMP算法 * * @param T 主串（text） * @param P 模式串（pattern） * @return 模式串在主串中呈现的地位，如未呈现则返回-1 */public static int KMP(String T, String P) {    char[] t = T.toCharArray();    char[] p = P.toCharArray();    int i = 0; // 主串的地位指针    int j = 0; // 模式串的地位指针    int[] next = getNext(P);    while (i < t.length && j < p.length) {        if (j == -1 || t[i] == p[j]) { // 若匹配或j为初始值，i、j指针后移            i++;            j++;        } else {            j = next[j]; // 若不匹配，i不变，j回退到指定地位        }    }    if (j == p.length) // 匹配胜利        return i - j;    else // 匹配失败        return -1;}public static int[] getNext(String P) {    char[] p = P.toCharArray();    int[] next = new int[p.length];    next[0] = -1;    int j = 0;    int k = -1;    while (j < p.length - 1) {        if (k == -1 || p[j] == p[k]) {            k++;            j++;            next[j] = k;        } else {            k = next[k];        }    }    return next;}

五、求模式串呈现次数

有一个文本串T，和一个模式串P，当初要求P在T中的呈现次数。

本例见：NC149 KMP算法

咱们晓得，原先退出while循环的条件是i == t.length或j == p.length。

若要求P在T中的呈现次数，则当j == p.length时不应该退出循环，而是应该进行以下操作：

  • 记录次数的count值加一；
  • i指针、j指针回退一位；
  • j指针向左挪动，心愿用模式串的前缀去匹配文本串的后缀，即j = next[j]。这一步的思考过程与求next数组中的k = next[k]统一，不赘述。

因而能够失去NC149 KMP算法该例中的代码：

import java.util.*;public class Solution {    public int kmp(String S, String T) {        char[] s = S.toCharArray();        char[] t = T.toCharArray();        int[] next = getNext(S);        int i = 0;        int j = 0;        int count = 0;        while (i < t.length) {            if (j == -1 || t[i] == s[j]) {                i++;                j++;            } else {                j = next[j];            }            if (j == s.length) {                count++;                i--;                j--;                j = next[j];            }        }        return count;    }    public int[] getNext(String S) {        char[] s = S.toCharArray();        int[] next = new int[s.length];        next[0] = -1;        int k = -1;        int j = 0;        while (j < s.length - 1) {            if (k == -1 || s[k] == s[j]) {                k++;                j++;                next[j] = k;            } else {                k = next[k];            }        }        return next;    }}

六、参考资料

  1. 尚硅谷：Java数据结构与算法
  2. KMP算法详解