KMP（The Knuth-Morris-Pratt Algorithm）算法用于字符串匹配，從字符串中找出給定的子字符串。但它并不是很好理解和掌握。而理解它概念中的部分匹配表，是理解 KMP 算法的關鍵。 這里的討論繞開其背后晦澀難懂的邏輯，著重從其運用上來理解它。 字符串查找比如從字符串 abcdef 中找出 abcdg 子字符串。 樸素的解法，我們可以這樣做， - 分別取出第一位進行匹配，如果相同再取出各自的第二位。
- 如果不同，則將索引后移一位，從總字符串第二位開始，重復步驟一。
這種樸素解法的弊端在于，每次匹配失敗，索引只后移一位，有很多冗余操作，效率不高。 在進行第一輪匹配中，即索引為 0 時，我們能夠匹配出前四個字符 abcd 是相等的，后面發現想要的 g 與真實的 e 不符，標志著索引為 0 的情況匹配失敗，開始查看索引為 1 時，但因為我們在第一輪匹配中，已經知道了總字符串中前四個字符的長相，但還是需要重復地挨個進行匹配。 部分匹配表/Partial Match Table以長度為 8 的字符串 abababca，為例，其部分匹配表格為： char: | a | b | a | b | a | b | c | a |
index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 | 其中 value 行便是部分匹配表的值。 子集對于上面示例字符串，假如我們觀察第 index 為 2 的位置，那么我們得到了字符串的一個子集 aba，如果我們觀察 index 為 7 的位置，那得到的是整個字符串，這點是很顯然的。當我們觀察的位置不同時，表示我們關注的字符串中的子集不同，因為子字符串發生了變化。 前綴 & 后綴對于給定的字符串，從末尾開始去掉一個或多個字符，剩下的部分都叫作該字符串的真前綴（Proper prefix），后面簡稱前綴。這里「真」不是「真·前綴」的意思，聯想一下數學里面集合的「真子集」。比如 banana，其前綴有： 同理，從首部開始，去掉一個或多個字條，剩下的部分是該字符串的真后綴（Proper suffix）。還是 banana，其后綴有： 部分匹配值可以看到，所有前綴和后綴在數量上是對稱的，那么我們可以從前綴中找出一個，與后綴進行匹配，先不關心做這個匹配的意義。以最開始的文本 abababca 為例。 假如我們觀察 index 為 2 的位置，此時子字符串為 aba，其前后綴分別為： 將前綴依次在后綴中去匹配，這里前后綴列表中能夠匹配上的只有 a 這個子字符串，其長度為 1，所以將這個觀測結果填入表中記下來，與開始看到的部分匹配表吻合了。 再比如來觀察 index 為 3 的位置，此時得到的子字符串為 abab，此時的前后綴為： 此時可觀察出其匹配項為 ab，長度為 2，也與上面部分匹配表中的值吻合。 再比如來觀察 index 為 5 的位置，此時子字符串為 ababab，前后綴為： - 前綴：
a，ab，aba，abab，ababa - 后綴：
babab，abab，bab，ab，b
然后拿前綴中每個元素與后綴中的元素進行匹配，最后找出有兩個匹配項， 我們取長的這個 abab，其長度為 4。 所以現在再來看上面的部分匹配表，一是能理解其值是怎么來的，二是能理解其表示的意義，即，所有前綴與后綴的匹配項中長度最長的那一個的長度。 當我們繼續，進行到 index 為 6 時，子字符串為 abababc，可以預見，前后綴中找不到匹配。因為所有前綴都不包含 c，而所有后綴都包含 c。所以此時部分匹配值為 0。 再繼續就到字符串末尾了，即整個字符串 abababca。也可以預見，因為所有前綴都以 a 開始，并且所有后綴都以 a 結尾，所以此時的部分匹配值最少為 1。繼續會發現，因為后面的后綴開始有 c 的加入，使得后綴都包含 ca，而前綴中能夠包含 c 的只有 abababc，而該長度 7 與同等長度的后綴 bababca 不匹配。至此就可以得出結論，匹配結果就是 1，沒有更長的匹配了。 部分匹配表的使用利用上面的部分匹配值，我們在進行字符串查找時，不必每次失敗后只移動一位，而是可以移動多位，去掉一些冗余的匹配。這里有個公式如下： If a partial match of length partial_match_length is found and table[partial_match_length] > 1, we may skip ahead partial_match_length - table[partial_match_length - 1] characters.
如果匹配過程中，匹配到了部分值為 partial_match_length，即目前找出前 partial_match_length 個字符是匹配的，將這個長度減一作為部分匹配表格中的 index 代入，查找其對應的 value 即 table[partial_match_length-1]，那么我們可以向前移動的步長為 partial_match_length - table[partial_match_length - 1]。 下面是本文開始時的那個部分匹配表: char: | a | b | a | b | a | b | c | a |
index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 | 假設需要從 bacbababaabcbab 中查找 abababca，根據上面的公式我們來走一遍。 首次匹配發生在總字符串的第二個字符， bacbababaabcbab |
abababca 此時匹配的長度為 1，部分匹配表中索引為 1-1=0 的位置對應的部分匹配值為 0，所以我們可以向前移動的距離是 1-0 1。其實也相當于沒有跳躍，就是正常的本次匹配失敗，索引后移一位的情況。這里沒有節省任何成本。 繼續直到再次發生匹配，此時匹配到的情況如下： bacbababaabcbab |||||
abababca 現在匹配到的長度是 5，部分匹配表中 5-1=4 對應的部分匹配值為 3，所以我們可以向前移動 5-3=2，此時一下子就可以移動兩位了。 上一次的位置 | 最新移動到的位置 | |bacbababaabcbab
xx|||
abababca 此時匹配到的長度為 3， 查找到 table[partial_match_length-1] 即 index 為 2 對應的值為 1，所以可向前移動的距離為 3-1=2。 bacbababaabcbab
xx|
abababca 此時我們需要查找的字符串其長度已經超出剩余可用來匹配的字符串了，所以可直接結束匹配，得到結論：沒有查找到結果。 Javascript 中的實現以下是來自 trekhleb/javascript-algorithms 中 JavaScript 版本的 KMP 算法實現： 相關教程：Javascript視頻教程 //**
* @see https://www.youtube.com/watch?v=GTJr8OvyEVQ
* @param {string} word
* @return {number[]}
*/
function buildPatternTable(word) {
const patternTable = [0];
let prefixIndex = 0;
let suffixIndex = 1;
while (suffixIndex < word.length) {
if (word[prefixIndex] === word[suffixIndex]) {
patternTable[suffixIndex] = prefixIndex + 1;
suffixIndex += 1;
prefixIndex += 1;
} else if (prefixIndex === 0) {
patternTable[suffixIndex] = 0;
suffixIndex += 1;
} else {
prefixIndex = patternTable[prefixIndex - 1];
}
}
return patternTable;
}
/**
* @param {string} text
* @param {string} word
* @return {number}
*/
export default function knuthMorrisPratt(text, word) {
if (word.length === 0) {
return 0;
}
let textIndex = 0;
let wordIndex = 0;
const patternTable = buildPatternTable(word);
while (textIndex < text.length) {
if (text[textIndex] === word[wordIndex]) {
// We've found a match.
if (wordIndex === word.length - 1) {
return (textIndex - word.length) + 1;
}
wordIndex += 1;
textIndex += 1;
} else if (wordIndex > 0) {
wordIndex = patternTable[wordIndex - 1];
} else {
wordIndex = 0;
textIndex += 1;
}
}
return -1;
}
時間復雜度
因為算法中涉及兩部分字符串的線性對比，其時間復雜度為兩字符串長度之和，假設需要搜索的關鍵詞長度為 k，總字符串長度為 m，則時間復雜度為 O(k+m)。 | 
