【Java 数据结构算法】宁可累死自己, 也要卷死别人 17 KMP 算法

本文主要是介绍【Java 数据结构算法】宁可累死自己, 也要卷死别人 17 KMP 算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【Java 数据结构 & 算法】⚠️宁可累死自己, 也要卷死别人 17⚠️ KMP 算法

概述
KMP 算法
部分匹配表
KMP 算法实现

概述

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

在这里插入图片描述

KMP 算法

KMP (Knuth-Morris-Pratt), 是一种改进的字符串匹配算法. KMP 算法解决了暴力匹配需要高频回退的问题, KMP 算法在匹配上若干字符后, 字符串位置不需要回退, 从而大大提高效率. 如图: 在这里插入图片描述
举个例子 (字符串 “abcabcdef” 匹配字符串 “abcdef”):

次数	暴力匹配	KMP 算法	说明
1	`a`bcabcdef `a`bcdef	`a`bcabcdef `a`bcdef	a 和 a 匹配
2	`ab`cabcdef `ab`cdef	`ab`cabcdef `ab`cdef	ab 和 ab 匹配
3	`abc`abcdef `abc`def	`abc`abcdef `abc`def	abc 和 abc 匹配
4	abc`a`bcdef abc`d`ef	abc`a`bcdef abc`d`ef	abca 和 abcd 不匹配, 回退. 暴力匹配回退到索引 1, 即 “b”, KMP 算法索引跳置 3, 即 “a”
5	a`b`cabcdef `a`bcdef	abc`a`bcdef `a`bcdef	暴力匹配 b 和 a 不匹配, 后移. KMP 算法 a 和 a 匹配
6	ab`c`abcdef `a`bcdef	abc`ab`cdef `ab`cdef	暴力匹配 c 和 a 不匹配, 后移. KMP 算法 ab 和 ab 匹配
7	abc`a`bcdef `a`bcdef	abc`abc`def `abc`def	暴力匹配 a 和 a 匹配. KMP 算法 abc 和 abc 匹配
8	abc`ab`cdef `ab`cdef	abc`abcd`ef `abcd`ef	暴力匹配 ab 和 ab 匹配. KMP 算法 abcd 和 abcd 匹配
9	abc`abc`def `abc`def	abc`abcde`f `abcde`f	暴力匹配 abc 和 abc 匹配. KMP 算法 abcde 和 abcde 匹配
10	abc`abcd`ef `abcd`ef	abc`abcdef abcdef`	暴力匹配 abcd 和 abcd 匹配. KMP 算法 abcdef 和 abcdef 匹配 , 匹配完成
11	abc`abcde`f `abcde`f	abc`abcdef abcdef`	暴力匹配 abcde 和 abcde 匹配. KMP 算法匹配完成
12	abc`abcdef abcdef`	abc`abcdef abcdef`	暴力匹配 abcd 和 abcd 匹配, 匹配完成. KMP 算法匹配完成

部分匹配表

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

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

字符串	前缀	后缀	共同部分	值
A	NaN	NaN	NaN	0
AB	A	B	NaN	0
ABC	A, AB	C, BC	NaN	0
ABCD	A, AB, ABC	D, CD, BCD	NaN	0
ABCDA	A, AB, ABC, ABCD	A, DA, CDA, BCDA	A	1
ABCDAB	A, AB, ABC, ABCD, ABCDA	B, AB, DAB, CDAB, BCDAB	AB	2
ABCDAB	A, AB, ABC, ABCD, ABCDA, ABCDAB	D, BD, ABD, DABD, CDABD, BCDABD	NaN	0

在这里插入图片描述

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, jint 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回退到-1j = -1;}}return next;}public static void main(String[] args) {// 字符串1String str1 = "BBCABCDAB ABCDABD";// 字符串2String str2 = "ABCDABD";// 匹配表int[] next = getNext(str2);System.out.println(Arrays.toString(next));// KMP算法int result = Match(str1, str2, next);System.out.println(result);}
}

输出结果: