Link

题解

不会 T1/hanx

首先对 \(S\) 串 KMP 一波。

假如我们已经填好了 \(T\) 的前 \(i\) 个字符，并设 \(T_{1\sim i}\) 与 \(S\) 的相同长度前缀相等的最长后缀长度为 \(j\)，那么当且仅当 \(S\) 的长度为 \(j,nxt_j,nxt_{nxt_j},……\) 的前缀与 \(T_{1\sim i}\) 的对应长度相同的后缀相等。

考虑确定了 \(T_{i+1}\) 之后，\(j\) 肯定会发生变化。我们设 \(to_{j,c}\) 为 \(S\) 与 \(T\) 的前缀的最长公共前后缀的长度为 \(j\) 时，在末尾新加一个字符 \(c\) 后，最长公共前后缀长度变成了什么，预处理出来即可。

知道了最长公共前后缀，我们也可以轻松算出会使 \(T_{1\sim i}\) 的哪些后缀的 \(\text{LCP}\) 加一，这个也可以和 \(to_{j,c}\) 一起预处理，然后就可以直接 dp 了。

时间复杂度：\(O(26nm)\)

AC code

http://www.nfls.com.cn:10611/submission/225869