乐趣区

关于java:Java算法系列KMP算法三

jiezi

【写在后面】

“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 算法详解
退出移动版