这里是KMP算法的原文:http://www.cnblogs.com/huangxincheng/archive/2012/12/01/2796993.html
我根据原文理解,修改为java版的....
"那么kmp算法比红黑树还要变态,很抱歉,每次打kmp的时候,输入法总是提示“看毛片”三个字,嘿嘿,就叫“看毛片算法”吧。"
我这边也是:
多的就不用说了,直接上代码:
1 /**
2 *
3 */
4 package com.b510;
5
6 /**
7 * kmp算法
8 *
9 * @date 2012-12-1 <br />
10 * @author hongten(hongtenzone@foxmail.com)
11 *
12 */
13 public class KMPAlgorithm {
14
15 public static void main(String[] args) {
16 // ababcabababdc
17 String[] zstr = { "a", "b", "a", "b", "c", "a", "b", "a", "b", "a", "b", "d", "c" };
18 // babdc
19 String[] mstr = { "b", "a", "b", "d", "c" };
20
21 int index = KMP(zstr, mstr);
22
23 if (index == -1) {
24 System.out.println("没有匹配的字符串!");
25 } else {
26 System.out.println("哈哈,找到字符啦,位置为:" + index);
27 }
28 }
29
30 public static int KMP(String[] bigstr, String[] smallstr) {
31 int i = 0;
32 int j = 0;
33
34 // 计算“前缀串”和“后缀串“的next
35 int[] next = GetNextVal(smallstr);
36
37 while (i < bigstr.length && j < smallstr.length) {
38 if (j == -1 || bigstr[i] == smallstr[j]) {
39 i++;
40 j++;
41 } else {
42 j = next[j];
43 }
44 }
45
46 if (j == smallstr.length) {
47 return i - smallstr.length;
48 }
49
50 return -1;
51 }
52
53 public static int[] GetNextVal(String[] smallstr) {
54 // 前缀串起始位置("-1"是方便计算)
55 int k = -1;
56
57 // 后缀串起始位置("-1"是方便计算)
58 int j = 0;
59
60 int[] next = new int[smallstr.length];
61
62 // 根据公式: j=0时,next[j]=-1
63 next[j] = -1;
64
65 while (j < smallstr.length - 1) {
66 if (k == -1 || smallstr[k] == smallstr[j]) {
67 // pk=pj的情况: next[j+1]=k+1 => next[j+1]=next[j]+1
68 next[++j] = ++k;
69 } else {
70 // pk != pj 的情况:我们递推 k=next[k];
71 // 要么找到,要么k=-1中止
72 k = next[k];
73 }
74 }
75 return next;
76 }
77
78 }
运行结果: