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

65次阅读

共计 4292 个字符,预计需要花费 11 分钟才能阅读完成。

【写在后面】

“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.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 算法详解

正文完
 0