|
kmp（the knuth-morris-pratt algorithm）算法用于字符串匹配，从字符串中找出给定的子字符串。但它并不是很好理解和掌握。而理解它概念中的部分匹配表，是理解 kmp 算法的关键。 这里的讨论绕开其背后晦涩难懂的逻辑，着重从其运用上来理解它。 字符串查找比如从字符串 朴素的解法，我们可以这样做，
这种朴素解法的弊端在于，每次匹配失败，索引只后移一位，有很多冗余操作，效率不高。 在进行第一轮匹配中，即索引为 0 时，我们能够匹配出前四个字符 部分匹配表/Partial Match Table以长度为 8 的字符串 其中 子集对于上面示例字符串，假如我们观察第 前缀 & 后缀对于给定的字符串，从末尾开始去掉一个或多个字符，剩下的部分都叫作该字符串的真前缀（Proper prefix），后面简称前缀。这里「真」不是「真·前缀」的意思，联想一下数学里面集合的「真子集」。比如
同理，从首部开始，去掉一个或多个字条，剩下的部分是该字符串的真后缀（Proper suffix）。还是
部分匹配值可以看到，所有前缀和后缀在数量上是对称的，那么我们可以从前缀中找出一个，与后缀进行匹配，先不关心做这个匹配的意义。以最开始的文本 假如我们观察
将前缀依次在后缀中去匹配，这里前后缀列表中能够匹配上的只有 再比如来观察
此时可观察出其匹配项为 再比如来观察
然后拿前缀中每个元素与后缀中的元素进行匹配，最后找出有两个匹配项，
我们取长的这个 所以现在再来看上面的部分匹配表，一是能理解其值是怎么来的，二是能理解其表示的意义，即，所有前缀与后缀的匹配项中长度最长的那一个的长度。 当我们继续，进行到 再继续就到字符串末尾了，即整个字符串 部分匹配表的使用利用上面的部分匹配值，我们在进行字符串查找时，不必每次失败后只移动一位，而是可以移动多位，去掉一些冗余的匹配。这里有个公式如下： 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. 如果匹配过程中，匹配到了部分值为 下面是本文开始时的那个部分匹配表: @@######@@假设需要从 首次匹配发生在总字符串的第二个字符， @@######@@此时匹配的长度为 1，部分匹配表中索引为 1-1=0 的位置对应的部分匹配值为 0，所以我们可以向前移动的距离是 继续直到再次发生匹配，此时匹配到的情况如下： @@######@@现在匹配到的长度是 5，部分匹配表中 5-1=4 对应的部分匹配值为 3，所以我们可以向前移动 5-3=2，此时一下子就可以移动两位了。 @@######@@此时匹配到的长度为 3， 查找到 3-1=2。 @@######@@此时我们需要查找的字符串其长度已经超出剩余可用来匹配的字符串了，所以可直接结束匹配，得到结论：没有查找到结果。 Javascript 中的实现以下是来自 trekhleb/javascript-algorithms 中 JavaScript 版本的 KMP 算法实现： 相关教程：Javascript视频教程 @@######@@时间复杂度 因为算法中涉及两部分字符串的线性对比，其时间复杂度为两字符串长度之和，假设需要搜索的关键词长度为 k，总字符串长度为 m，则时间复杂度为 O(k+m)。 |
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 |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 |
abababcabacbababaabcbab |||||
abababca 上一次的位置 | 最新移动到的位置 | |bacbababaabcbab
xx|||
abababcabacbababaabcbab
xx|
abababca//**
* @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;
}
