Vault 101

xjay2007's Blog

0%

KMP算法理解

发表于 更新于 分类于

克努斯-莫里斯-普拉特算法（Knuth-Morris-Pratt 算法，简称 KMP 算法），是常用的字符串搜索算法之一。

部分匹配表

部分匹配表（Partial Match Table），又称为失配函数（Failure Function）。

假设有个字符串 "abababca"，可以得出它的部分匹配表为：

s:         | a | b | a | b | a | b | c | a |
index:     | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
table:     | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |

其中的 table[i] 表示子模式串 s[0...i] 的匹配值。例如：i = 5，子模式串就是 string[0:5] = "ababab"，它的匹配表 table[5] = 4。

在此之前，解释一下模式串的前缀和后缀。

前缀（Proper prefix）：字符串从首位开始的所有子串，不包括最后一个字符。例如："hello" 的前缀有："h"、"he"、"hel"、"hell"。

后缀（Proper suffix）：字符串到末尾结束的所有子串，不包括第一个字符。例如：”world” 的后缀有："orld"、"rld"、"ld"、"d"。

jBoxer 的这篇文章，用一句话解释了其中的部分匹配表的实质。

The length of the longest proper prefix in the (sub)pattern that matches a proper suffix in the same (sub)pattern.

子模式串的前缀和后缀的共同元素中最长元素的长度。

例

例如：上面的字符串 "abababca"，对子模式串 s[0:4] = "ababa" 来说，它的前缀有：

["a", "ab", "aba", "abab"]

后缀有：

["baba", "aba", "ba", "a"]

可以看出其中的共同元素为 ["a", "aba"]，其中最长元素为 "aba"，它的长度为 3 ，所以它的部分匹配表 table[4] = 3。

部分匹配表作用

暴力匹配算法中，遇到不匹配的字符，将模式串向前移动一位，重新开始比较。

在 KMP 算法中，在遇到不匹配的字符时，根据部分匹配表中的值，将模式串向前移动，跳过不必要的匹配。

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.

如果进行到模式串的第 i 个字符不匹配，即已部分匹配到的长度为 len = i，并且 table[len] > 0，那么下一步匹配可以跳过 len - table[len-1] 个字符。

例

以 "abababca" 为例，可以得出它的部分匹配表：

s:         | a | b | a | b | a | b | c | a |
index:     | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
table:     | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |

目标字符串为 "bacbababaabcbab"，第一次匹配位置：

// 绿色为已匹配字符，红色为不匹配字符，黄色为跳过字符
                  1
index:  012345678901234
m:      bacbababaabcbab
         |
s:       abababca
index:   01234567
table:   00123401

因为 s[1] != m[2] ，已部分匹配的模式串 "a" 长度为 len = 1。部分匹配表中 table[len-1] 即 table[0] 的值为 0，所以不需要跳过字符，只需将指向母串字符的指针加一。下一个匹配位置如下：

// 绿色为已匹配字符，红色为不匹配字符，黄色为跳过字符
                  1
index:  012345678901234
m:      bacbababaabcbab
            |||||
s:          abababca
index:      01234567
table:      00123401

已部分匹配的模式串 "ababa" 长度为 len = 5。部分匹配表中 table[5-1] 即 table[4] 值为 3。所以需要向前跳过 len - table[4] = 5 - 3 = 2 个字符：

// 绿色为已匹配字符，红色为不匹配字符，黄色为跳过字符
                  1
index:  012345678901234
m:      bacbababaabcbab
            xx|||
s:            abababca
index:        01234567
table:        00123401

此时部分匹配的模式串变为 "aba" 长度为 len = 3。table[3-1] = table[2] 值为 1，所以需要向前跳过 len - table[2] = 3 - 1 = 2 个字符：

// 绿色为已匹配字符，红色为不匹配字符，黄色为跳过字符
                  1
index:  012345678901234
m:      bacbababaabcbab
              xx|
s:              abababca
index:          01234567
table:          00123401

此时模式串的长度已经超过了母串的剩余字符数，所以余下的字符无法匹配。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// JavaScript
/**
 * 构造部分匹配表
 * @param {string} pattern 
 * @returns {number[]}
 */
function buildPartialMatchTable(pattern) {
    const length = pattern.length;
    // 前缀和后缀的共同元素的最长长度
    let len = 0;
    let table = new Array(length).fill(0);

    // 从 1 开始计算
    let i = 1;
    while(i < length) {
        if(pattern[i] === pattern[len]) {
            len++;
            table[i] = len;
            i++;
        } else { // pattern[i] !== pattern[len]
            // 
            if(len !== 0) {
                len = table[len - 1];
                // 这里 i 不加一
            } else { // len === 0
                table[i] = 0;
                i++;
            }
        }
    }
    return table;
}
/**
 * KMP搜索
 * @param {string} s 
 * @param {string} pattern 
 * @returns {number}
 */
function kmpSearch(s, pattern) {
    const table = buildPartialMatchTable(pattern);
    
    let [i, j] = [0, 0];
    while(i < s.length) {
        if(s[i] === pattern[j]) {
            i++;
            j++;
        } 
        if(j === pattern.length) {
            return i - j;
        } else if(i < s.length && s[i] !== pattern[j]) {
            if (j > 0) {
                // j = j - (j - table[j - 1]);
                j = table[j - 1];
            } else {
                i++;
            }
        }
    }
    return -1;
}

参考链接

相似文章