KMP，字符串算法万恶的源头

_2eyks · 2025-10-28 20:21:28 · 个人记录

默认下文所有字符串的下标从 1 开始。下文用 s[l\dots r] 表示 s_l,s_{l+1},\dots,s_r 顺次拼接出的字符串，即 s 在下标区间 [l,r] 内的子串。

学会 KMP，要先学会求 border。

border 是一个字符串 s 对应的长度为 |s| 的数组。对 \text{border}_i 的定义为：在字符串 t=s[1\dots i] 中，使得 t[1\dots v]=t[i-v+1\dots i] 的最大可能值 v（需要满足 v\neq i）。

其求法为：假设当前已经求出了 \text{border}_1,\text{border}_2,\dots,\text{border}_{i-1}，需要求 \text{border}_i，则定义一个值 tp，初始 tp=\text{border}_{i-1}，进行下面的操作：

• 如果 s_{tp+1}=s_i，则 \text{border}_i 就是 tp，赋值并结束操作。
• 反之，让 tp\leftarrow \text{border}_{tp}。
• 如果此时 tp=0，则 \text{border}_i=0，结束操作，否则回到第一步继续操作。

其实就是一个让 s[1\dots tp+1] 与 s[i-tp\dots i] 不断匹配的过程，这里的 tp 满足 s[1\dots tp]=s[i-tp\dots i-1]。复杂度感性理解就是线性的。

至此，border 已经求完了。

:::info[代码]

fo(i,1,n){
    int tp=border[i-1];
    while (tp&&s[i]!=s[tp+1])
        tp=border[tp];
    if (s[i]==s[tp+1])
        tp++;
    border[i]=tp*(i>1);
}

:::

在字符串 s 中匹配 t 字符串的做法是类似的，如果 s_{i+1} 与 t_{tp+1} 匹配，就 tp\leftarrow tp+1；否则就让 tp\leftarrow \text{border}_{tp}，继续匹配。复杂度也是线性的。

KMP 算法可以用来优化 dp。比如
P3082 这个题，在求出 border 之后，dp 的过程相当于 KMP 匹配字符串的算法，可以优化时间复杂度。