【Java算法系列】KMP算法（三） java算法kmp

【写在前面】
“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）的问题。
【【Java算法系列】KMP算法（三）】在开始学习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; } }

六、参考资料