学习笔记：KMP 自动机

喵仔牛奶 · 2025-01-07 08:29:09 · 算法·理论

Solution

这个叫 KMP 自动机。

考虑对于一个字符串 s 求出 fail 数组。令 s_{[l,r]}=s_ls_{l+1}\cdots s_r，令 fl_i 是 s_{[1,i]} 的最长 border，令 S(i) 表示 s_{[1,i]} 的 border 集合加上 i 自己。

考虑设 nx_{i,j}，具体地：

\max_{i\in S(i)\land s_{i+1}=j}\{i\}+1 & \exist i\in S(i)\land s_{i+1}=j \\ 0 & \text{otherwise} \end{cases}

也就是 nx_{i,j} 表示在 s_{[1,i]} 后面加入 j 字符后的最长 border。考虑已经求出了 [1,i) 的 fl_i 和 [1,i-1) 的 nx_{i,j}（因为 nx_{i,j} 和 s_{i+1} 有关），现在要求出 fl_i 和 nx_{i-1,j}。

首先求出 fl_i，可以发现 fl_i=nx_{fl_{i-1},s_i}，这个推一下 KMP 的过程，是一样的。你发现 fl_{i-1}<i-1，所以 nx_{fl_{i-1},j} 已经推出。一个 corner case 是 i=1，此时 fl_0=0，特判即可（当然可以发现不判也是对的）。

接下来求 nx_{i-1,j}。对于 j\neq s_i，nx_{i-1,j}=nx_{fl_{i-1},j}；而对于 j=s_i，nx_{i-1,j}=i。

然后你就求完了。可以发现这个算法以 \mathcal{O}(\lvert\Sigma\rvert) 的时间完成了加入字符、求出 border 的任务。好处是不需要均摊，可以做带撤销 KMP。

参考代码：

REP(i, 1, n) {
    fl[i] = nx[fl[i - 1]][s[i] - 'a'];
    REP(j, 0, 25) nx[i - 1][j] = nx[fl[i - 1]][j];
    nx[i - 1][s[i] - 'a'] = i;
}

例题：CF1721E。