1 public static String kmp(String haystack, String needle) {
 2         if (needle.length() == 0) return haystack;
 3         if (haystack.length() == 0) return null;
 4         if (haystack.length() < needle.length()) return null;
 5         
 6         int[] next = new int[needle.length()];
 7         next = kmpNext(needle);
 8         
 9         for (int i = 0, j = 0; i < haystack.length(); i++) {
10           while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
11               j = next[j - 1];
12           }
13           
14           if (haystack.charAt(i) == needle.charAt(j))
15               j++;
16           //match successfully
17           if (j == needle.length())
18               return haystack.substring(i-j+1);
19       }
20       return null;
21     }
22 
23     public static int[] kmpNext(String needle) {
24         int[] next = new int[needle.length()];
25         if (needle.length() == 0) return next;
26         next[0] = 0;
27         for (int i = 1, j = 0; i < needle.length(); ++i) {
28             while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
29                 j = next[j - 1];
30             }
31 
32             if (needle.charAt(i) == needle.charAt(j)) 
33                 ++j;
34 
35             next[i] = j;
36         }
37         return next;
38     }