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 }