[toc]

KMP算法

1. 应用场景-字符串匹配问题

  1. 有一个字符串 str1= "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好"
  2. 和一个子串 str2="尚硅谷你尚硅你"
  3. 现在要判断 str1 是否含有 str2, 如果存在,就返回第一次出现的位置, 如果没有,则返回-1。

2. 暴力匹配算法

如果用暴力匹配的思路,并假设现在 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. 用暴力方法解决的话就会有大量的回溯,每次只移动一位,若是不匹配,移动到下一位接着判断,浪费了大量的时间。

2.1 代码实现

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
package cn.itbuild.kmp;

public class ViolenceMatch {

public static void main(String[] args) {
String str1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好";
String str2 = "尚硅谷你尚硅谷你";
int result = violenceMatch(str1,str2);
System.out.println(result);
}

/**
* 进行暴力匹配
* @param str1
* @param str2
* @return
*/
public static int violenceMatch(String str1,String str2) {

char[] chars1 = str1.toCharArray();
char[] chars2 = str2.toCharArray();

// 获取两个字符串的长度
int str1Len = chars1.length;
int str2Len = chars2.length;

// i索引指向chars1,j索引指向chars2
int i = 0;
int j = 0;
// 防止数组下标越界
while(i<str1Len && j<str2Len) {
// 如果两字符串i,j位相匹配,则i++,j++即比较下一位
if (chars1[i] == chars2[j]) {
i++;
j++;
}else {
i = i - (j -1);
j = 0;
}
}

// 如果j==str2Len则说明匹配到了
if (j == str2Len) {
return i - j;
}else {
return -1;
}

}
}

3. KMP算法介绍

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

4. KMP算法最佳应用-字符串匹配问题

字符串匹配问题::

  1. 一个字符串 str1= "BBCABCDAB ABCDABCDABDE",和一个子串 str2="ABCDABD"
  2. 现在要判断 str1 是否含有 str2, 如果存在,就返回第一次出现的位置, 如果没有,则返回-1
  3. 要求:使用 KMP 算法完成判断,不能使用简单的暴力匹配算法。

4.1 思路分析图解

KMP

4.2 代码实现

  • public static int kmpSearch(String str1,String str2); KMP字符串匹配方法
  • public static int[] kmpNext(String str) 获取str字符串(子串)的部分匹配值表
  • j = next[j-1];<——–j > 0 && str1.charAt(i) != str2.charAt(j)
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
package cn.itbuild.kmp;

public class KMPAlgorithm {

public static void main(String[] args) {
String str1 = "BBC ABCDABABCDABCDABDE";
String str2 = "ABCDABD";
int index = kmpSearch(str1, str2);
System.out.println(index);
}

/**
*
* @param str1
* @param str2
* @return
*/
public static int kmpSearch(String str1,String str2) {

// 获取str2字符串的部分匹配值表
int[] next = kmpNext(str2);

for (int i = 0,j = 0; i < str1.length(); i++) {

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

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

// 说明匹配到了
if (j == str2.length()) {
return i - j + 1;
}

}


return -1;
}

/**
* @param str
* @return 获取str字符串(子串)的部分匹配值表
*/
public static int[] kmpNext(String str) {
// 创建一个next 数组,保存部分匹配值
int[] next = new int[str.length()];
// 如果字符串是长度为1,部分匹配值就为 1
next[0] = 0;

for (int i = 1,j = 0; i < str.length(); i++) {

// 当 str.charAt(i) != str.charAt(j) ,我们需要从 next[j-1]获取新的 j
// 直到我们发现 有 str.charAt(i) == str.charAt(j)成立才退出
// 这时 kMP算法的核心点
while(j>0 && str.charAt(i) != str.charAt(j)) {
j = next[j-1];
}

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

next[i] = j;
}

return next;
}
}