前言
KMP 算法是 D.E.Knuth、J,H,Morris 和 V.R.Pratt 三位神人共同提出的，称之为 Knuth-Morria-Pratt 算法，简称 KMP 算法。该算法相对于 Brute-Force（暴力）算法有比较大的改进，主要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高。
然后，坑啊，KMP这东西我看了一天才给我整明白一点，现在还有点恍惚，我心态差点崩了，呜呜
代码
KMP算法的核心部分主要是或者模式串的前缀，什么意思呢，就是比如：abcabf 那么，对应的他们的前缀表next是[0,0,0,0,1,2]。
比较抽象，可以把他看做这个字符串给它两个指针 j、k 分别对应他们前缀和后缀，然后一一比对，找到他们的最大公共字符串，很离谱吧。 而像这样的 第一位、第二位一般都是0，因为他们前后都不一样嘛
我的理解就是：
1
2
3
4
5
6
7
8
9
10
| abcabf
abcabf
看这两个，错开了，两个错开比对，第一个是后缀，相对应的第一个位置不要了
第二个就是前缀了
首先是 b跟a比，不同，则 0
c跟b比 0
以此类推
KMP最核心的就是求next了，而最长的公共 就是 下面前缀的长度了，如果不相同，把对应的next位置的写入前缀公共长
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public static int[] getNext(String ps) {
char[] p = ps.toCharArray();
int[] next = new int[p.length];
next[0] = -1;
int j = 0;
int k = -1;
while (j<p.length -1){
if(k == -1 || p[j] == p[k]){
j++;
k++;
next[j] = k;
}else {
k = next[k];
}
}
return next;
}
|
KMP的主函数就太简单了，作为暴力美学的延伸，有了next前缀表，那么J就不必回溯，就直接让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
| public static int kmp(String ts,String ps){
char[] t = ts.toCharArray();
char[] p = ps.toCharArray();
int[] next = getNext(ps);
int i = 0;
int j = 0;
while (i<t.length && j<p.length){
if(j == -1 || t[i] == p[j]){
i++;
j++;
}else{
j = next[j];
}
}
if(j == p.length){
return i-j;
}else {
return -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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| public class KMP {
public static void main(String[] args){
String ts = "abcabcabf";
String ps = "abcabf";
int begin_place = kmp(ts,ps);
System.out.println(begin_place);
}
public static int kmp(String ts,String ps){
char[] t = ts.toCharArray();
char[] p = ps.toCharArray();
int[] next = getNext(ps);
int i = 0;
int j = 0;
while (i<t.length && j<p.length){
if(j == -1 || t[i] == p[j]){
i++;
j++;
}else{
j = next[j];
}
}
if(j == p.length){
return i-j;
}else {
return -1;
}
}
public static int[] getNext(String ps) {
char[] p = ps.toCharArray();
int[] next = new int[p.length];
next[0] = -1;
int j = 0;
int k = -1;
while (j<p.length -1){
if(k == -1 || p[j] == p[k]){
j++;
k++;
next[j] = k;
}else {
k = next[k];
}
}
return next;
}
}
|
结尾
KMP算法让我头疼，让我死吧。膜拜发明此算法的大佬，到底是怎么想到的，我爱了。