Version: Next

KMP

KMP 是 Knuth-Morris-Pratt 的简称，取自三位发明人的名字，于 1977 年提出

直接跳到下一个以 1 开头的位置

  • 与蛮力法相比，KMP 的精妙之处在于：充分利用先前比较过的内容，可以聪明地跳过一些不必要比较的位置

KMP —— next 表的使用

  • KMP 会预先根据 模式串 的内容生成一张 next 表（一般是一个数组）
  • 对于模式串 ABCDABCE，其 next 表为：
模式串字符ABCDABCE
索引01234567
元素-10000123

如果遇到了在 模式串 的靠后位置匹配失败的情况

  • 对于蛮力法，需要将 pi 清零，ti 回退，中间比较操作全部相当于白做
  • KMP 则会查询 next 表，根据 模式串出现匹配失败的字符索引—— pi，在 next 进行查询。对于此处的 pi = 7 和上文给出的 next 表，明显可知此时从表中查出的值是 3
  • 大幅移动 模式串，直接跳过 文本串 的部分字符，通过 pi - next[pi] 实现，此处等于 7 - 3 = 4
  • 接下来将 next[pi] 的值赋值给 pi，即 pi = next[pi]，此时 pi = 3。达到的效果为 从模式串先前实配的位置开始比较，先前匹配成功的字符直接不比了

KMP 核心原理

  • A、B 为子串；c、d、e 为单个字符
  • 当 d、e 失配时，如果希望 模式串 能够一次性向右移动一大段距离，然后直接比较 d、c 字符
    • 前提条件是 A串 必须等于 B串
  • 因此，KMP 必须在失配字符 e 左边的子串中找出符合条件的 A、B，从而得知向右移动的距离
  • 向右移动的记录：e左边字符串的长度 - A串的长度 = e的索引 - c的索引
  • c的索引：等于 next[e的索引]，所以向右移动的距离：e的索引 - next[e的索引]
总结
  • 如果在 pi 位置失配，向右移动的距离是 pi - next[pi]，所以 next[pi] 越小，移动幅度越大
  • next[pi] 是 pi 左边子串的真前缀后缀的最大公共子串长度

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

模式串真前缀真后缀最大公共子串长度
ABCDABCEA、AB、ABC、ABCD、ABCDA、ABCDAB、ABCDABCBCDABCE、CDABCE、DABCE、ABCE、BCE、CE、E0
ABCDABCA、AB、ABC、ABCD、ABCDA、ABCDABBCDABC、CDABC、DABC、ABC、BC、C3
ABCDABA、AB、ABC、ABCD、ABCDABCDAB、CDAB、DAB、AB、B2
ABCDAA、AB、ABC、ABCDBCDA、CDA、DA、A1
ABCDA、AB、ABCBCD、CD、D0
ABCA、ABBC、C0
ABAB0
A--0

将上表压缩为一个数组

模式串字符ABCDABCE
最大公共子串长度00001230
  • 第一行，到哪个字符，就表示以该字符结尾的 子串
  • 元素值表示该 子串 对应的子串长度

例如：下图就表示 子串 ABCDABC 对应的真前缀后缀最大公共子串长度为 3

得到 next 表

将最大公共子串长度都向右移动 1 位，首字符设置为 -1， 就得到了 next 表

模式串字符ABCDABCE
索引01234567
元素-10000123

构建 next 表

对于一个模式串，n、i 为图中两个字符的下标，则 next[i] == n，因为 next 表存储着 i 索引对应字符左侧子串的真前缀后缀最大公共子串长度，该长度在数值上恰好等于索引 n

  1. 如果 pattern[i] == pattern[n]，索引 i 位置的字符 与 索引 n 位置的字符 相同，则：
    • next[i + 1] == n + 1
  2. 如果 pattern[i] != pattern[n]，索引 i 位置的字符 与 索引 n 位置的字符 不相同，则：
    • 在 A串 右侧虚拟放置一个字符，其下标索引为 k，则可认为 A串 的长度为 k
    • 则 next[n] == k，因为索引 n 左侧的真前后缀最大公共子串此时为 A串，而 A串 的长度为 k
    • 如果 pattern[i] == pattern[k]，则如图所示，next[i + 1] = k + 1
    • 如果 pattern[i] != pattern[k]：将 k 带入 n ，重复执行 2.

实现

KMP
public static int indexOf(String text, String pattern) {
if (text == null || pattern == null) return -1;
char[] textChars = text.toCharArray(); // 转成字符数组
char[] patternChars = pattern.toCharArray();
int tlen = textChars.length;
int plen = patternChars.length;
// 如果模式串长度大于 文本串长度 返回 -1
if (tlen == 0 || 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) {
if (pi < 0 || textChars[ti] == patternChars[pi]) {
pi++;
ti++;
} else { // 失配
pi = next[pi];
}
}
return (pi == plen) ? (ti - pi) : -1;
}
/**
* 生成并返回 next 表
*
* @param pattern 模式串
* @return next 表
*/
private static int[] next(String pattern) {
char[] chars = pattern.toCharArray();
int len = chars.length;
int[] next = new int[chars.length];
next[0] = -1;
int i = 0;
int n = -1;
int iMax = len - 1; // 下表最大值为 长度 - 1
while (i < iMax) { // 没有=号，因为循环体里有 ++i
if (n < 0 || chars[i] == chars[n]) {
next[++i] = ++n;
} else {
n = next[n];
}
}
return next;
}