Algorithm KMP

Knuth Morris Pratt (KMP) is an algorithm, which checks the characters from left to right. When a pattern has a sub-pattern appears more than one in the sub-pattern, it uses that property to improve the time complexity, also for in the worst case.

前言

    KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。

KMP算法

暴力匹配算法(效率低)

用暴力匹配的思路,并假设现在str1匹配到 i 位置,子串str2匹配到 j 位置,则有:
1)如果当前字符匹配成功(即str1[i] == str2[j]),则i++,j++,继续匹配下一个字符;
2)如果失配(即str1[i]! = str2[j]),令i = i - (j - 1),j = 0。相当于每次匹配失败时,i 回溯,j 被置为0;
3)用暴力方法解决的话就会有大量的回溯,每次只移动一位,若是不匹配,移动到下一位接着判断,浪费了大量的时间。(不可行!)

KMP算法(效率高)

1)KMP是一个解决模式串在文本串是否出现过,如果出现过,最早出现的位置的经典算法;
2)Knuth-Morris-Pratt 字符串查找算法,简称为 “KMP算法”,常用于在一个文本串S内查找一个模式串P 的出现位置,这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表,故取这3人的姓氏命名此算法;
3)KMP方法算法就利用之前判断过信息,通过一个next数组,保存模式串中前后最长公共子序列的长度,每次回溯时,通过next数组找到,前面匹配过的位置,省去了大量的计算时间。

KMP分析:


KMP代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
import java.util.Arrays;

/**
* @Auther: Arsenal
* @Date: 2020-03-28 20:25
* @Description: KMP算法
*/
public class KMP {
public static void main(String[] args) {
String text = "KMP是一个解决模式串在文本串是否出现过";
String pattern = "解决模式";
int[] next = kmpNext("ABCDABD"); //[0, 1, 2, 0]
System.out.println("next=" + Arrays.toString(next));
//int index = violenceMatch(text, pattern);
int index = kmpMatch(text, pattern, next);
System.out.println("index=" + index);
}

/**
* kmp搜索算法(效率高)
* @param text 源字符串
* @param pattern 子串
* @param next 部分匹配表, 是子串对应的部分匹配表
* @return 如果是-1就是没有匹配到,否则返回第一个匹配的位置
*/
public static int kmpMatch(String text, String pattern, int[] next) {

//遍历
for (int i = 0, j = 0; i < text.length(); i++) {

//需要处理 str1.charAt(i) != str2.charAt(j), 去调整j的大小
//KMP算法核心点, 可以验证...
while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
j = next[j - 1];
}

if (text.charAt(i) == pattern.charAt(j)) {
j++;
}
if (j == pattern.length()) {//找到了 // j = 3 i
return i - j + 1;
}
}
return -1;
}

/**
* 获取到一个字符串(子串) 的部分匹配值表
* @param pattern 子串
* @return
*/
public static int[] kmpNext(String pattern) {
//创建一个next 数组保存部分匹配值
int[] next = new int[pattern.length()];
next[0] = 0; //如果字符串是长度为1 部分匹配值就是0
for (int i = 1, j = 0; i < pattern.length(); i++) {
//当dest.charAt(i) != dest.charAt(j) ,我们需要从next[j-1]获取新的j
//直到我们发现 有 dest.charAt(i) == dest.charAt(j)成立才退出
//这时kmp算法的核心点
while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
j = next[j - 1];
}

//当dest.charAt(i) == dest.charAt(j) 满足时,部分匹配值就是+1
if (pattern.charAt(i) == pattern.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}

/**
* 暴力匹配(回溯多,效率低)
* @param text 被匹配的字符串
* @param pattern 匹配的字符串
* @return 下标
*/
public static int violenceMatch(String text, String pattern) {
char[] texts = text.toCharArray();
char[] patterns = pattern.toCharArray();
int textsLen = texts.length;
int patternsLen = patterns.length;
int i = 0;
int j = 0;

while (i < textsLen && j < patternsLen) {

if (texts[i] == patterns[j]) { //匹配
i++;
j++;
} else { //不匹配
//如果失配(即str1[i]! = str2[j]),令i = i - (j - 1),j = 0。相当于每次匹配失败时,i 回溯,j 被置为0。
i = i - (j - 1);
j = 0;
}
}

if (j == patternsLen) { //匹配
return i - j;
} else { //不匹配
return -1;
}
}
}

延伸

    KMP 算法详解
    很详尽KMP算法
    kmp算法-百度百科
    KMP算法图文详解
    韩顺平数据结构和算法
    Knuth-Morris-Pratt Algorithm
    图解kmp算法-通俗易懂kmp算法

Content
  1. 1. 前言
  2. 2. KMP算法
  3. 3. 延伸