算法-KMP

 1 public class Solution {
 2     public String strStr(String haystack, String needle) {
 3 
 4         int i = 0;
 5         int hlength = haystack.length();
 6         int nlength = needle.length();
 7 
 8         if (nlength == 0) {
 9             return haystack;
10         } else {
11             int[] form = KMPform(needle);
12 
13             while (i <= hlength - nlength) {
14                 int j = 0;
15                 while (j < nlength) {
16                     if (haystack.charAt(i + j) != needle.charAt(j)) {
17                         if (j == 0) {
18                             i++;
19                         } else {
20                             i = i + j - form[j - 1]-1;
21                         }
22                         break;
23                     } else if (j == nlength - 1) {
24                         return haystack.substring(i);
25                     }
26                     j++;
27                 }
28             }
29             return null;
30         }
31     }
32     
33     public int[] KMPform(String str) {
34         int[] form = new int[str.length()];
35         form[0] = -1;
36         for (int i = 1; i < form.length; i++) {
37             int index = form[i - 1];
38             while (index >= 0 && str.charAt(i) != str.charAt(index + 1))
39             {
40                 index = form[index];
41             }
42             if (str.charAt(i) == str.charAt(index + 1))
43             {
44                 form[i] = index + 1;
45             }
46             else
47             {
48                 form[i] = -1;
49             }
50         }
51         return form;
52     }
53 
54 }