原理：

示例：leetcode:Implement strStr()

 

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             else47             {48                 form[i] = -1;49             }50         }51         return form;52     }53 54 }