KMP算法JAVA的实现

1. public class KMP {   
2.        
3.     private String text;   
4.     private String pattern;   
5.        
6.     KMP() {   
7.            
8.     }   
9.        
10.     KMP(String text, String pattern) {   
11.         this.text = text;   
12.         this.pattern = pattern;   
13.     }   
14.        
15.     public void setText(String text) {   
16.         this.text = text;   
17.     }   
18.        
19.     public void setPattern(String pattern) {   
20.         this.pattern = pattern;   
21.     }   
22.        
23.     public void KMPMatcher() {   
24.         int n = text.length();   
25.         int m = pattern.length();   
26.            
27.         int prefix[] = computePrefix();   
28.         int q = 0;   
29.            
30.         int count = 0;   
31.         for(int i = 0; i < n; i++) {   
32.                
33.             while(q > 0 && pattern.charAt(q)!= text.charAt(i)) {   
34.                 q = prefix[q -1];   
35.             }   
36.                
37.             if(pattern.charAt(q) == text.charAt(i))   
38.                 q++;   
39.                
40.             if(q == m) {   
41.                 System.out.println("Pattern occurs with shift  " + ++count + "times");   
42.                 q = prefix[q - 1];   
43.             }   
44.         }   
45.            
46.         if(count == 0) {   
47.             System.out.println("There is no matcher!");   
48.         }   
49.     }   
50.        
51.     private int[] computePrefix() {   
52.         int length = pattern.length();   
53.         int[] prefix = new int[length];   
54.            
55.         prefix[0] = 0;   
56.            
57.         int k = 0;   
58.         for(int i = 1; i < length; i++) {   
59.             while(k > 0 && pattern.charAt(k) != pattern.charAt(i)) {   
60.                 k = prefix[k -1];    
61.             }   
62.             if(pattern.charAt(k) == pattern.charAt(i))   
63.                 k++;   
64.             prefix[i] = k;   
65.         }   
66.            
67.         return prefix;   
68.     }   
69.        
70.     public static void main(String[] args) {   
71.            
72.         KMP kmp;   
73.            
74.         if(args.length == 2) {   
75.             kmp = new KMP(args[0] , args[1]);   
76.         }   
77.         else {   
78.             kmp = new KMP();   
79.             kmp.setText("ababacabacbababababacabcbabababaca");   
80.             kmp.setPattern("ababaca");   
81.         }   
82.            
83.         kmp.KMPMatcher();   
84.            
85.     }