Last active
March 31, 2019 14:19
-
-
Save david-zw-liu/22e1b84a99fc6d333ae71867336c8aae to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// | |
// 建立 pattern 的最大共同前後綴表 | |
// | |
// 假設 pattern 為 ABCABA | |
// 建立的順序如下 | |
// A 0 | |
// AB 0 | |
// ABC 0 | |
// ABCA 1 | |
// ABCAB 2 | |
// ABCABA 1 | |
// | |
// 主要有兩個重點: | |
// 1. 可以透過前一次的最大前後綴結果來推算這一次的最大前後綴長度 | |
// 舉例來說: | |
// 當 'ABCA' 變成 'ABCAB' 的時候, | |
// 其實只是在後面多加一個 B, | |
// 這時候只要比較前一個的 最大共同後綴長度+1 個字(B) 和 新加入的 B 是否匹配, | |
// 就可以決定此輪的最大共同前後綴長度了。 | |
// | |
// 2. 失配時,目前比較的 char 要再比較一次第一個 char | |
// 舉例來說: | |
// 當 'ABCAB' 變成 'ABCABA' 的時候, | |
// 根據第一點,比較的基準 C 和新加入的 A 發生了失配, | |
// 這代表與前一輪的最大共同前後綴沒有匹配, | |
// 但不代表這一輪沒有最大共同前後綴, | |
// 有可能與第一個字元 A 發生了匹配。 | |
// | |
function getFailures(pattern) { | |
let failures = [0]; | |
let i = 0 | |
let j = 1 | |
while(j < pattern.length) { | |
if (pattern[i] === pattern[j]) { | |
failures[j] = failures[j-1] + 1; | |
i++; | |
} else { | |
i = 0; | |
failures[j] = (pattern[i] === pattern[j]) ? 1 : 0; | |
} | |
j++; | |
} | |
return failures; | |
} | |
function kmp(str, pattern) { | |
if(str.length < pattern.length) return -1; | |
const failures = getFailures(pattern); // 取得 failure table | |
let strIdx = 0; | |
while(strIdx < str.length) { // 搜尋的 HEAD 尚未達到目標字串尾則繼續 loop | |
for(let patternIdx = 0; patternIdx < pattern.length; patternIdx++) { // 從 HEAD 開始比較 pattern 字串 | |
if (strIdx + patternIdx >= str.length) return -1; // 超出目標字串尾則代表沒有符合 | |
if (str[strIdx + patternIdx] !== pattern[patternIdx]) { // 目前 pattern 第 n 個 char 不符合 字串 HEAD + n 的 char | |
let commonSufPrefixLength = failures[patternIdx - 1] || 0; // 透過 failures 表來取得最大共同前後綴長度 (以已經匹配的 index 為基準) | |
strIdx += 1 + patternIdx - commonSufPrefixLength; // 移動 strIdx 略過失配的部分 | |
break; // 失配則離開 pattern 比對的 loop | |
} | |
if(patternIdx + 1 === pattern.length) { // 若 pattern 成功匹配,則回傳當前 strIdx | |
return strIdx; | |
} | |
} | |
} | |
return -1; | |
} | |
exports.kmp = kmp; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment