Java 数据结构与算法系列精讲之KMP算法

概述

从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章.

KMP 算法

KMP (Knuth-Morris-Pratt), 是一种改进的字符串匹配算法. KMP 算法解决了暴力匹配需要高频回退的问题, KMP 算法在匹配上若干字符后, 字符串位置不需要回退, 从而大大提高效率. 如图:

举个例子 (字符串 “abcabcdef” 匹配字符串 “abcdef”):

部分匹配表

部分匹配表 (Partial Match Table) 指的是 “前缀” 和 “后缀” 的最长共有元素的长度.

举个例子, 字符串 “ABCDABD” 的前缀与后缀:

KMP 算法实现

重点:

KMP 算法中移动的位数 = 已匹配的字符数 - 对应的部分匹配值

import java.util.Arrays;

public class KMPMatch {

public static int Match(String str1, String str2, int[] next) {

// 初始化索引
       int i = 0;
       int j = 0;

for (; i < str1.length(); i++) {

if (j > 0 && str1.charAt(i) != str2.charAt(j)) {
               // 不匹配, 回退
               i = i - next[j - 1];
               j = 0;
           }

// 匹配
           if (str1.charAt(i) == str2.charAt(j)) {
               j++;
           }

// 返回索引
           if (j == str2.length()) {
               return i - j + 1;
           }
       }
       return -1;
   }

// 部分匹配
   public static int[] getNext(String s) {

// 定义数组
       int next[] = new int[s.length()];

// 初始化i, j
       int i = 0;
       int j = -1;
       next[0] = -1;

// 遍历
       while (i < s.length() - 1) {
           if (j == -1 || s.charAt(i) == s.charAt(j)) {
               // 匹配成功
               next[i] = j + 1;
               i++;
               j++;
           } else {
               //一旦不匹配成功j回退到-1
               j = -1;
           }
       }
       return next;
   }

public static void main(String[] args) {

// 字符串1
       String str1 = "BBCABCDAB ABCDABD";

// 字符串2
       String str2 = "ABCDABD";

// 匹配表
       int[] next = getNext(str2);
       System.out.println(Arrays.toString(next));

// KMP算法
       int result = Match(str1, str2, next);
       System.out.println(result);
   }
}

输出结果:

[0, 0, 0, 0, 1, 2, 0]
10

来源：https://iamarookie.blog.csdn.net/article/details/122105073