KMP 是一个字符串匹配算法, 最终是找到字符串 \(S\) 中子串 \(W\) 的起始索引地址, 下面我们假设:
string S = "ABCAABCDABCABCDABDABDE";
string W = "ABCDABD";KMP 的核心, 部分匹配表 (Partial Match Table, PMT)
为什么要提出 PMT 呢? 其目的是为了不让 \(S\) 中的字符匹配超过一次, 也就是说 \(S\) 中的字符在整个算法过程中只会进行一次比较. 我们在了解 PMT 之前要先知道两个概念, Proper suffixes 和 Proper prefixes (这两种字符串既不是空串, 也不是原字符串)
Proper prefix: 不包括字符串尾部一个或多个字符的子串, 我们叫前缀集合,
Proper suffix: 不包括字符串前面一个或多个字符的子串, 我们叫后缀集合.
那 PMT 的定义就是, PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度. 以 \(W\) 举例, 则有:
| A | 无 | 无 | 0 |
| AB | A | B | 0 |
| ABC | A, AB | BC, C | 0 |
| ABCD | A, AB, ABC | BCD, CD, D | 0 |
| ABCDA | A, AB, ABC, ABCD | BCDA, CDA, DA, A | 1 |
| ABCDAB | A, AB, ABC, ABCD, ABCDA | BCDAB, CDAB, DAB, AB, B | 2 |
| ABCDABD | A, AB, ABC, ABCD, ABCDA, ABCDAB | BCDABD, CDABD, DABD, ABD, BD, D | 0 |
我们得到 pmt[W.length()] = { 0, 0, 0, 0, 1, 2, 0 }.
如何使用 PMT ?
我们使用 PMT 来避免多余的匹配操作. 如果我们前面已经匹配了 partial_match_length (下面省略为 pml)长度了, 下面我们开始匹配 S 和 W, 始终要注意的是主串的索引 i 只要匹配成功就会有 i = i + 1,
ABCAABCDABCABCDABDABDE
|||+
ABCDABD在比较到第四个字符时发生失配, 这是 pml 是 3, 3 - pmt[pml - 1] 即 3 - pmt[2] 是 0, 则,
ABCAABCDABCABCDABDABDE
|-
ABCDABD在 pml 为 1 后失配, pml[pml - 1] 即 pmt[0] 是 0, 则,
ABCAABCDABCABCDABDABDE
||||||-
ABCDABD这次匹配到 W 的最后一个字符时失配了, pml = 6, pmt[pml - 1] = pmt[5] = 2
ABCAABCDABCABCDABDABDE
|-
ABCDABD此时, pml = 1, pmt[pml - 1] = pmt[0] = 0
ABCAABCDABCABCDABDABDE
|||||||
ABCDABD匹配结束.
在 Ref2 中解释说 " pmt[pml] > 1, 我们可以跳过 pml - pmt[pml - 1] 个字符", 其实没有必要, 我们从 pmt 中得到的值就是下一次开始比较的 W 起始索引. 如果为 1 则必定会从 W 的起始部分开始比较.