KMP算法假定了解案件的原则，其实很easy。
KMP算法简述
关于根据自己的理解在这里。
KMP该算法由三个发明人的名称（Knuth、Morris、Pratt）的首字母组成，又称字符串查找算法。
个人认为能够理解为最小回溯算法，即匹配失效的时候，尽量少回溯。从而缩短时间复杂度。
KMP算法有两个关键的地方。1）求解next数组。2）利用next数组进行最小回溯。
1）求解next数组
当k=-1的时候。表示找不到这种最长前缀。
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| p | a | b | a | a | b | c | a | b | a |
| next[j] | -1 | -1 | 0 | 0 | 1 | -1 | 0 | 1 | 2 |
- t = next[ j - 1 ] + 1，t 指向可能等于 p[ j ] 的位置，即 p[ t ] 可能等于 p[ j ]。
- 假设 p[ t ] = p[ j ] ， 那么 next[ j ] = next[ j - 1 ] + 1
- 假设 p[ t ] != p[ j ] ， 则令 t = next[ t - 1 ] + 1，继续第 2 步直到 t = 0 或者找到位置。
- 结束时推断p[ t ] 是否等于 p[ j ] ，假设等于则 next[ j ] = t ， 否则等于 -1 。
下图表示了第一次不匹配。第二次匹配的过程，其他过程能够类推。当中 或 覆盖部分表示最长匹配串。 为待判定位置， 为已判定位置。
2）利用next数组进行最小回溯
s ××××××××××××××××××××××××××××××××××××××××××××
p ××××××××××××××
在j处不失配时，前面的有部分匹配。这时须要利用next数组信息进行最小回溯。
s ××××××××××××××××××××××××××××××××××××××××××××
p ××××××××××××××
（这里 i 指向 s ， j 指向 p。）
注意在 j = 0 的时候失配时。直接 i++ 就可以。
当 j > 0 的时候，须要利用next数组最快找到 p[ j ] == s[ i ] 的位置。
假设 j 移动到了0还找不到。则 i++，然后继续匹配。
这里我们能够发现仅仅有 j 回溯了，i没有回溯，可是因为普通版本号的 KMP 算法 j 须要不停地回溯直到找到合适的回溯位置，因此速度不是特别快。还能够继续优化。感兴趣的读者能够想想怎样事先求解好next数组从而不须要不停地回溯。
代码实现
strStr返回的是首次匹配的地址。假设不能匹配则返回NULL。
class Solution {public: vector getNext(char* &s){ vector next(strlen(s), -1); for(int i=1; i =0) j = next[j]; if(s[j+1] == s[i]) next[i] = j+1; // else 默觉得-1 } return next; } char *strStr(char *haystack, char *needle) { if(haystack==NULL || needle==NULL) return NULL; if(strlen(haystack) < strlen(needle)) return NULL; if(strlen(needle) == 0) return haystack; vector next = getNext(needle); int i = 0; int j = 0; int haystackLen = strlen(haystack); int needleLen = strlen(needle); while(i 因为有人问有没有java版本号的，因为鄙人java比較挫。写java时部分还写成了scala的语法。不知道代码是否规范，有优化的地方还麻烦java方面的大神指点。
import java.util.*;public class StrStrSolution { private List getNext(String p){ List next = new ArrayList (); next.add(-1); for(int i=1; i =0) j = next.get(j); if(p.charAt(j+1) == p.charAt(i)) next.add( j + 1 ); else next.add( -1 ); } return next; } public String strStr(String haystack, String needle) { if (haystack == null || needle == null) return null; if (needle.length() == 0) return haystack; if (needle.length() > haystack.length()) return null; List next = getNext(needle); int i = 0; int j = 0; int haystackLen = haystack.length(); int needleLen = needle.length(); while(i < haystackLen && j < needleLen){ if(haystack.charAt(i) == needle.charAt(j) ) { i++; j++; if(j == needleLen) return haystack.substring(i - j); }else{ if(j==0) i++; else j = next.get(j-1)+1; } } return null; } public static void main(String[] args) { String s = "babcabaabcacbac"; String p = "abaabcac"; StrStrSolution sol = new StrStrSolution(); System.out.println(sol.strStr(s,p)); }} 