KMP

基础的字符串匹配算法.

先看暴力匹配 —— 如果一个位置失配了,则把整个模式串往前移一位,然后从头开始匹配.

这很有效,这很复杂,因为每次都要重新遍历模式串.

所以 kmp 就是尝试解决这样的问题的方法 —— 如何在失配的时候利用已经匹配的信息减少时间复杂度呢?

pi 数组

在详细说明算法流程之前,先看一下整个算法最核心的部分.

我们先定义pi数组为 —— pi[i] = P[0...i]中,最长相等的真前缀和真后缀的长度.

非常拗口,也难以说明定义原因.

前缀和后缀

假设有字符串 abac, 则它的逐个前缀分别为 ——

a
ab
aba
abac

后缀分别为 ——

c
ac
bac
abac

那么”真“即表示和原串不相等的子串(可以类比子集和真子集的概念)

计算例子

假设有模式串ababaca

i = 0, "a"
无 真前后缀 pi[0] = 0;

i = 1, "ab"
前缀:
	a
后缀:
	b
不相等, pi[1] = 0;

i = 2, "aba"
前缀:
	a
	ab
后缀:
	a
	ba
其中 "a" = "a" 所以 pi[2] = len("a") = 1;

i = 3, "abab"
前缀:
	a
	ab
	aba
后缀:
	b
	ab
	bab
其中"ab" = "ab" 所以 pi[3] = len("ab") = 2

之后往后迭代同理

算法解释与流程

所以pi数组本质上是维护了模式串中”相同的前缀和后缀长度“,那么假设在失配的时候,我们是中间的某一部分失配,但是前面是匹配成功的,我们可以利用这已经匹配成功的部分.

假设i是匹配串的下标,j是模式串的下标,那么如果第j位失配了,说明P[0...j - 1]是匹配成功的,我们就可以复用这一部分 —— 由于知道pi[j - 1]表示P[0..j - 1]这段上最长的真前缀和真后缀长度,所以可以不再把j重新归零开始重新做匹配,而是利用重复的前后缀“把相同的前缀搬挪到对应相同的后缀部分”,也就是j = pi[j - 1],这样就可以不再从头开始匹配,而是跳过前缀那些已经匹配过的部分,直接继续从不同的位置进行匹配 —— “刚才文本中匹配成功的尾巴,直接继续当作模式串开头使用”

pi 数组构造

这里比较奇妙的,也不是暴力去枚举构造 pi 数组,而是“使用 P 自己去匹配 P 自己”

i 指向当前要处理的位置，可以看作后缀部分的末尾。
j 表示当前已经匹配成功的前缀长度。

假设 P 还是上面不变,那么

• 初始的时候使用子串a(P 的第一位)去匹配匹配串a, 失配,说明现在还是j = 0
• 一直迭代到 a 去匹配 aba, 发现有一个相等的位置了,于是 j += 1, j = 1
• 此时相当于使用ab去继续对 P 进行匹配

(说的有点乱,但是非常妙)

给出一份模板参考

vector<int> buildPi(const string& pattern)
{
    int n = pattern.size();
    vector<int> pi(n, 0);

    // j 表示当前已经匹配成功的前缀长度
    int j = 0;

    // pi[0] 一定为 0，所以从 i = 1 开始
    for (int i = 1; i < n; ++i)
    {
        // 如果当前字符 pattern[i] 无法接在 pattern[j] 后面，
        // 说明长度为 j 的 border 不能继续扩展。
        // 于是回退到更短的候选 border。
        while (j > 0 && pattern[i] != pattern[j])
        {
            j = pi[j - 1];
        }

        // 如果可以接上，说明 border 长度增加 1
        if (pattern[i] == pattern[j])
        {
            ++j;
        }

        // 记录 pattern[0...i] 的最长相等真前后缀长度
        pi[i] = j;
    }

    return pi;
}

总结

先进行一个复杂度分析 —— 假设

• n = 文本串 S 的长度
• m = 模式串 P 的长度

则

• 时间复杂度：O(n + m) (构造 pi 数组和正式进行匹配)
• 空间复杂度：O(m)

然后做算法核心就是合理利用已经有的信息,避免重复计算

抛去字符串的限制,实际上对于序列问题都可以使用(