KMP 算法

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\) 举例, 则有:

我们得到 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 的起始部分开始比较.

References:

1. https://en.wikipedia.org/wiki/Substring
2. http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/

KMP 算法

原文：https://www.cnblogs.com/x5lcfd/p/11703384.html