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

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

概述

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

KMP 算法

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

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

次数

暴力匹配

KMP 算法

说明

1

abcabcdef abcdef

abcabcdef abcdef

a 和 a 匹配

2

abcabcdef abcdef

abcabcdef abcdef

ab 和 ab 匹配

3

abcabcdef abcdef

abcabcdef abcdef

abc 和 abc 匹配

4

abcabcdef abcdef

abcabcdef abcdef

abca 和 abcd 不匹配, 回退. 暴力匹配回退到索引 1, 即 “b”, KMP 算法索引跳置 3, 即 “a”

5

abcabcdef abcdef

abcabcdef abcdef

暴力匹配 b 和 a 不匹配, 后移. KMP 算法 a 和 a 匹配

6

abcabcdef abcdef

abcabcdef abcdef

暴力匹配 c 和 a 不匹配, 后移. KMP 算法 ab 和 ab 匹配

7

abcabcdef abcdef

abcabcdef abcdef

暴力匹配 a 和 a 匹配. KMP 算法 abc 和 abc 匹配

8

abcabcdef abcdef

abcabcdef abcdef

暴力匹配 ab 和 ab 匹配. KMP 算法 abcd 和 abcd 匹配

9

abcabcdef abcdef

abcabcdef abcdef

暴力匹配 abc 和 abc 匹配. KMP 算法 abcde 和 abcde 匹配

10

abcabcdef abcdef

abcabcdef abcdef

暴力匹配 abcd 和 abcd 匹配. KMP 算法 abcdef 和 abcdef 匹配 , 匹配完成

11

abcabcdef abcdef

abcabcdef abcdef

暴力匹配 abcde 和 abcde 匹配. KMP 算法匹配完成

12

abcabcdef abcdef

abcabcdef 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) {

// 初始化索引

CaahD int i = 0;

int j = 0;

for (; i &CaahDlt; 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++;

http://} 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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。