KMP 算法与 border 浅记

终于完全明白了困扰多年的 KMP 算法，果然从 border 理论理解才是最好的。

因此写下本文，供自己复习。

border

首先给出 \(\text{border}\) 的定义：在字符串 \(S\) 中，最长的真公共前后缀。

显然，\(\text{border}\) 的 \(\text{border}\) 也是 \(S\) 的一个 \(\text{border}\)。

我们定义 \(\text{nxt}[i]\) 为 \(S[1\dots i]\) 的 \(\text{border}\)，考虑如何快速求 \(\text{nxt}\)。

假设我们现在已知 \(\text{nxt}[1\dots n]\)，想要求出 \(\text{nxt}[n+1]\)。

考虑 \(S[n+1]\) 和 \(S[\text{nxt}[n]+1]\) 是否匹配。如果匹配，那么显然。 \(\text{nxt}[n+1]=\text{nxt}[n]+1\)，否则我们继续考虑它是否可以和 \(\text{nxt}[\text{nxt}[n]]\) 匹配。我们一直匹配到成功即可。

这样可以均摊 \(O(n)\) 求出 \(\text{nxt}\)。

S = " " + S;

void get_nxt()
{
    nxt[0] = 0;
    int n = S.length();
    for(int i = 1; i < n; i++)
    {
        int j = nxt[i - 1];
        while(j > 0 && S[i] != S[j + 1]) j = nxt[j];
        if(S[i] == S[j + 1] && j + 1 < i) nxt[i] = j + 1;
    }
}

KMP

\(\text{KMP}\) 是用来快速匹配字符串的算法。

给定模式串 \(S\)，文本串 \(T\)，求 \(S\) 在 \(T\) 中所有匹配。

记 \(S\) 长度为 \(s\)，\(T\) 长度为 \(t\)。

我们将 \(S\) 和 \(\#\) 和 \(T\) 拼在一起，形成了 \(S\#T\) 的新字符串。我们求出来这个字符串的 \(\text{nxt}\)。

之后我们从 \(s+1\) 开始（即从 \(T\) 开始）遍历 \(\text{nxt}\)。如果 \(\text{nxt}[i] = s\)，那么这是一个成功的匹配。

时间复杂度 \(O(n+m)\)。