P3426 Solution

link

考虑 dp。设 \(dp_i\) 表示至 \(i\) 的字符串的答案。

KMP 求出 nxt 数组，那么显然 \(dp_i\) 要么等于 \(i\) 要么等于 \(dp_{nxt_i}\)。

什么时候 \(dp_i\) 等于 \(dp_{nxt_i}\) 呢？这时这个字符串一定由一个与 \(nxt_i\) 有相同 \(dp\) 值的前缀再印上一个 border 得到。 也就是说，当 \(\exists j,dp_j=dp_{nxt_i}\land j+nxt_i\ge i\) 时 \(dp_i=dp_{nxt_i}\)。

我们发现 \(j\) 越往右边时越容易满足的。于是在 dp 的同时维护 \(r_i=\max\{j|dp_j=i\}\)，转移时直接判断 \(r_{dp_{nxt_i}}\) 是否合法即可。