簡介
- KMP算法是一種字符串匹配算法冤留，由D.E.Knuth，J.H.Morris和V.R.Pratt同時發(fā)現(xiàn)拷肌，因此人們稱它為克努特——莫里斯——普拉特操作（簡稱KMP算法）馋袜。KMP算法的關鍵是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達到快速匹配的目的趁啸。具體實現(xiàn)就是實現(xiàn)一個next()函數(shù)强缘，函數(shù)本身包含了模式串的局部匹配信息。時間復雜度O(m+n)不傅。
算法分析
假設主串T用i指針遍歷旅掂，而模式串P用j指針遍歷。
和暴力法的區(qū)別
情況1：如果P[0]就不匹配了访娶，那么i指針指向下一位商虐，而j指針不變，這在暴力和KMP都一樣崖疤，不用多說秘车。
情況2：如果P的前幾個字符匹配的話，情況就有所不同劫哼。在暴力算法中叮趴，如果T[i] != P[j]，i需要回溯到i-j+1的位置权烧，而j變?yōu)?疫向。而在KMP算法中，則是利用已經(jīng)部分匹配的有效信息豪嚎，i指針不回溯搔驼，通過修改j指針，讓模式串移動到有效的位置侈询。
重點和難點
KMP算法的重點和難點是如何求j指針在不匹配時的下一位置舌涨，這里將該位置設為k。這里引入一個next數(shù)組扔字，next[j]表示P[j]匹配失敗后囊嘉，j指針應指向的位置温技，即next[j] = k。
分析
為什么要求k值呢扭粱？k值是怎么來的舵鳞？
當T[i] != P[j]時（j>0），已知P[0 ... j-1] == T[i-j ... i-1]琢蛤，若P[0 ... k-1] == P[j-k ... j-1]蜓堕，
則P[0 ... k-1] == T[i-k ... i-1]，此時只需將j指針移動到k博其，而i指針不需要移動套才，即可繼續(xù)進行比較。
所以此時問題轉化為求令P[0 ... k-1] == P[j-k ... j-1]的k的最大值慕淡，即P的前j個字符組成的子串的最長相同前綴后綴的長度（k）背伴。
next數(shù)組如何求
- 特殊情況：next[0] = -1（此時j不用動，i向后移一位）峰髓；next[1] = 0（此時i不用動傻寂，j回溯到第0位）；如果前j個字符都相同携兵，則next[j] = j-1疾掰。
- 其他情況：next[j] = k，其中k為P[0 ... j-1]中最長相同前綴后綴的長度
實戰(zhàn)：實現(xiàn)strStr()（LeetCode第28題）
題目描述
給定一個 haystack 字符串和一個 needle 字符串眉孩，在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個位置 (從0開始)个绍。如果不存在，則返回 -1浪汪。當 needle 是空字符串時我們應當返回 0 巴柿。這與C語言的 strstr() 以及 Java的 indexOf() 定義相符。
示例
示例1：
輸入: haystack = "hello", needle = "ll"
輸出: 2
示例2：
輸入: haystack = "aaaaa", needle = "bba"
輸出: -1
代碼
/**
* 利用KMP算法求解
*
* 需要進行匹配的字符（即haystack字符串）死遭，稱為主串广恢，簡稱T
* 模式（Pattern）字符串（即needle字符串），簡稱P
*
*/
private static int strStr_KMP(String haystack, String needle) {
if (needle.equals("")) {
return 0;
}
char [] T = haystack.toCharArray();
char [] P = needle.toCharArray();
int [] next = getNext(needle);
int i = 0;
int j = 0;
while (i < haystack.length() && j < needle.length()) {
if (j == -1 || T[i] == P[j]) { //當j == -1時呀潭，i向后移動一位钉迷，j也要歸零
i++;
j++;
} else { //T[i] != P[j]時，i指針不用動钠署，j指針移動到相應的位置
j = next[j];
}
}
if (j == needle.length()) { //說明在主串T中找到了模式串P
return i - j;
} else {
return -1;
}
}
/**
* 根據(jù)模式串P獲取next數(shù)組糠聪，next[j]表示P[j]匹配失敗后，j指針應指向的位置谐鼎。
*
* @param P 模式串
* @return next數(shù)組
*/
private static int [] getNext(String P) {
int [] next = new int[P.length()];
next[0] = -1;
int k = -1; //存儲當前next[j]對應的k值
int j = 0;
while (j < P.length()-1) {
if (k == -1 || P.charAt(k) == P.charAt(j)) { //隱含條件P[0 ... k-1] == P[j-k ... j-1]
//當k == -1時舰蟆，next[j++] = 0，例如next[1] = 0，或者前j字符沒有相同前綴后綴時也為0身害。
//當P[k] == P[j]時味悄，由于P[0 ... k-1] == P[j-k ... j-1]，則此時P[0 ... k] == P[j-k ... j]塌鸯，所以此時next[j+1] = k+1
next[++j] = ++k;
} else {
//當P[k] != P[j]時侍瑟，next[j+1]必定小于k，此時可以縮小k的值（最小小到-1）
k = next[k];
}
}
return next;
}
