KMP（The Knuth-Morris-Pratt Algorithm）算法用于字符串匹配，從字符串中找出給定的子字符串。但它并不是很好理解和掌握。而理解它概念中的部分匹配表，是理解 KMP 算法的關(guān)鍵。 這里的討論繞開其背后晦澀難懂的邏輯，著重從其運用上來理解它。 字符串查找比如從字符串 abcdef 中找出 abcdg 子字符串。 樸素的解法，我們可以這樣做， - 分別取出第一位進(jìn)行匹配，如果相同再取出各自的第二位。
- 如果不同，則將索引后移一位，從總字符串第二位開始，重復(fù)步驟一。
這種樸素解法的弊端在于，每次匹配失敗，索引只后移一位，有很多冗余操作，效率不高。 在進(jìn)行第一輪匹配中，即索引為 0 時，我們能夠匹配出前四個字符 abcd 是相等的，后面發(fā)現(xiàn)想要的 g 與真實的 e 不符，標(biāo)志著索引為 0 的情況匹配失敗，開始查看索引為 1 時，但因為我們在第一輪匹配中，已經(jīng)知道了總字符串中前四個字符的長相，但還是需要重復(fù)地挨個進(jìn)行匹配。 部分匹配表/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 的位置，那得到的是整個字符串，這點是很顯然的。當(dāng)我們觀察的位置不同時，表示我們關(guān)注的字符串中的子集不同，因為子字符串發(fā)生了變化。 前綴 & 后綴對于給定的字符串，從末尾開始去掉一個或多個字符，剩下的部分都叫作該字符串的真前綴（Proper prefix），后面簡稱前綴。這里「真」不是「真·前綴」的意思，聯(lián)想一下數(shù)學(xué)里面集合的「真子集」。比如 banana，其前綴有： 同理，從首部開始，去掉一個或多個字條，剩下的部分是該字符串的真后綴（Proper suffix）。還是 banana，其后綴有： 部分匹配值可以看到，所有前綴和后綴在數(shù)量上是對稱的，那么我們可以從前綴中找出一個，與后綴進(jìn)行匹配，先不關(guān)心做這個匹配的意義。以最開始的文本 abababca 為例。 假如我們觀察 index 為 2 的位置，此時子字符串為 aba，其前后綴分別為： 將前綴依次在后綴中去匹配，這里前后綴列表中能夠匹配上的只有 a 這個子字符串，其長度為 1，所以將這個觀測結(jié)果填入表中記下來，與開始看到的部分匹配表吻合了。 再比如來觀察 index 為 3 的位置，此時得到的子字符串為 abab，此時的前后綴為： 此時可觀察出其匹配項為 ab，長度為 2，也與上面部分匹配表中的值吻合。 再比如來觀察 index 為 5 的位置，此時子字符串為 ababab，前后綴為： - 前綴：
a，ab，aba，abab，ababa - 后綴：
babab，abab，bab，ab，b
然后拿前綴中每個元素與后綴中的元素進(jìn)行匹配，最后找出有兩個匹配項， 我們?nèi)￠L的這個 abab，其長度為 4。 所以現(xiàn)在再來看上面的部分匹配表，一是能理解其值是怎么來的，二是能理解其表示的意義，即，所有前綴與后綴的匹配項中長度最長的那一個的長度。 當(dāng)我們繼續(xù)，進(jìn)行到 index 為 6 時，子字符串為 abababc，可以預(yù)見，前后綴中找不到匹配。因為所有前綴都不包含 c，而所有后綴都包含 c。所以此時部分匹配值為 0。 再繼續(xù)就到字符串末尾了，即整個字符串 abababca。也可以預(yù)見，因為所有前綴都以 a 開始，并且所有后綴都以 a 結(jié)尾，所以此時的部分匹配值最少為 1。繼續(xù)會發(fā)現(xiàn)，因為后面的后綴開始有 c 的加入，使得后綴都包含 ca，而前綴中能夠包含 c 的只有 abababc，而該長度 7 與同等長度的后綴 bababca 不匹配。至此就可以得出結(jié)論，匹配結(jié)果就是 1，沒有更長的匹配了。 部分匹配表的使用利用上面的部分匹配值，我們在進(jìn)行字符串查找時，不必每次失敗后只移動一位，而是可以移動多位，去掉一些冗余的匹配。這里有個公式如下： 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 代入，查找其對應(yīng)的 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 | 假設(shè)需要從 bacbababaabcbab 中查找 abababca，根據(jù)上面的公式我們來走一遍。 首次匹配發(fā)生在總字符串的第二個字符， bacbababaabcbab |
abababca 此時匹配的長度為 1，部分匹配表中索引為 1-1=0 的位置對應(yīng)的部分匹配值為 0，所以我們可以向前移動的距離是 1-0 1。其實也相當(dāng)于沒有跳躍，就是正常的本次匹配失敗，索引后移一位的情況。這里沒有節(jié)省任何成本。 繼續(xù)直到再次發(fā)生匹配，此時匹配到的情況如下： bacbababaabcbab |||||
abababca 現(xiàn)在匹配到的長度是 5，部分匹配表中 5-1=4 對應(yīng)的部分匹配值為 3，所以我們可以向前移動 5-3=2，此時一下子就可以移動兩位了。 上一次的位置 | 最新移動到的位置 | |bacbababaabcbab
xx|||
abababca 此時匹配到的長度為 3， 查找到 table[partial_match_length-1] 即 index 為 2 對應(yīng)的值為 1，所以可向前移動的距離為 3-1=2。 bacbababaabcbab
xx|
abababca 此時我們需要查找的字符串其長度已經(jīng)超出剩余可用來匹配的字符串了，所以可直接結(jié)束匹配，得到結(jié)論：沒有查找到結(jié)果。 Javascript 中的實現(xiàn)以下是來自 trekhleb/javascript-algorithms 中 JavaScript 版本的 KMP 算法實現(xiàn)： 相關(guān)教程：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;
}
時間復(fù)雜度
因為算法中涉及兩部分字符串的線性對比，其時間復(fù)雜度為兩字符串長度之和，假設(shè)需要搜索的關(guān)鍵詞長度為 k，總字符串長度為 m，則時間復(fù)雜度為 O(k+m)。 | 
