【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)的问题。

在开始学习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 的图解如下:

【Java算法系列】KMP算法(三)_第1张图片

二、求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",求出其各个子串的部分匹配值:

【Java算法系列】KMP算法(三)_第2张图片

我们为什么要得到一个模式串的前缀后缀公共元素的长度表(部分匹配表)呢?这个表有什么用?接下来看以下模式串"ABCDABD"的字符串匹配的例子:

【Java算法系列】KMP算法(三)_第3张图片

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

因此,对于模式串"ABCDABD",初始化next[0] = -1,我们可以得到其next数组:

【Java算法系列】KMP算法(三)_第4张图片

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

【Java算法系列】KMP算法(三)_第5张图片

三、求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]。看下面一个例子:

      【Java算法系列】KMP算法(三)_第6张图片

      看第三步,当我们判断完前缀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.lengthj == 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算法详解

你可能感兴趣的