【算法漫笔003】浅谈KMP自动机+DP
普通的 KMP 显然无法嵌套入 DP 当中。尽管普通 KMP 的时间复杂度均摊为 O(N)O(N)O(N)（下文中所有 NNN 表示文本长度，MMM 表示模式串长度，RRR 表示字符集大小），但普通 KMP 的 while 回退只有在单条路径连续执行时才能均摊 O(1)O(1)O(1)，如果想要嵌套进 DP 里面，由于 DP 是多条路径并行枚举，均摊失效，时间复杂度可能来到 O(L×M2×R)O(L \times M^2 \times R)O(L×M2×R)。于是便有了 KMP自动机。
KMP自动机的原理
KMP 自动机的原理实际上和普通 KMP 相同，唯一的区别是在回退指针时，普通 KMP 使用一维的 nextnextnext 数组在匹配过程中动态计算并回退位置，while 执行 j=next[j-1]。
而 KMP 自动机则牺牲了一些空间复杂度，它将 nextnextnext 数组升级成二维，把所有可能的回退路径提前预处理，构建成二维的 nexti,jnext_{i,j}nexti,j ，表示已匹配长度为 j，读入字符 c 后的一步直达的最新状态。
显然两者在单次匹配的时间复杂度相同，但 KMP 自动机的空间复杂度比普通 KMP 花销更大，看起来似乎 KMP 自动机没有任何用处、可以被 KMP 取代，但事实真的如此吗？
KMP自动机+DP
原题链接：https://www.luogu.com.cn/problem/P3082
我们来看这样一道题，简化题意，即从 SSS 中选择一个最长的子序列，使得该序列不包含 TTT 这个连续子串，子序列的长度最长为多少。Tlen≤Slen≤104T_{len} \le S_{len} \le 10^4Tlen ≤Slen ≤104
容易想到 DPDPDP。我们设 dpi,jdp_{i,j}dpi,j 表示处理完 SSS 的前 iii 个字符后，当前选择的子序列与模式串 TTT 的最长可匹配前缀长度为 jjj 时，能够保留的最大字符数。
思考转移。
删除 SiS_iSi 的状态很容易，即状态不变，保留数也不变，则 dpi+1,j=max(dpi+1,j,dpi,j)dp_{i+1,j}=\max(dp_{i+1,j},dp_{i,j})dpi+1,j =max(dpi+1,j ,dpi,j )
保留 SiS_iSi 则需用到 KMP 自动机。查自动机转移表 nextj,Sinext_{j,S_i}nextj,Si 即可得到新状态 j′j'j′。
此时若 j′=Mj'=Mj′=M，说明拼接后出现了子串 TTT，转移非法，跳过。
否则可以直接进行转移，显然 dpi+1,j′=max(dpi+1,j′,dpi,j+1)dp_{i+1,j'}=\max(dp_{i+1,j'},dp_{i,j}+1)dpi+1,j′ =max(dpi+1,j′ ,dpi,j +1)
显然，初始化 dp0,0=0dp_{0,0}=0dp0,0 =0，其它为 −INF-INF−INF，答案即为 max(dpn,j)(0≤j≤M)\max(dp_{n,j})(0 \le j \le M)max(dpn,j )(0≤j≤M)。
但是我们能够发现，这个大小的数组显然会让我们陷入 MLE 的恐慌当中，此时我们只需要滚动数组即可。
这样你就成功的水过了一道青题。
提交记录：https://www.luogu.com.cn/record/294313545
总结
尽管 KMP 自动机从未作为核心考点出现在NOI、NOIP、CSP赛场上，但这的确是一个有趣的算法，能够优化一些结合字符串的区间 DP。而且万一下次就考了呢？
注释&致谢
感谢 StackEdit软件，欢迎大家去使用这个免费的 Markdown 编辑软件。它不仅可以在线使用，还可以下载使用。
今天没有注释o(￣▽￣)ブ
