后一题让我重新审视了一下前一道题我是怎么 A 掉的...

Problem

咕

Solution

动物园

重新审视一下几个数组的含义：

$nxt_i$ $0$~$i-1$ 的最长公共前后缀（不包括自身）

$cnt_i$ $0$~$i-1$ 的公共前后缀数目（可以重叠，包括自身 ）

$num_i$ $0$~$i-1$ 的不重叠公共前后缀数目

递推式：
$$cnt_i=cnt_{nxt_i}+1$$
$$num_i=cnt_{j} \ (\text{0~j- 1 属于 0~i- 1 的一个最大公共前后缀}, 2j\leq i)$$

似乎在梦中见过的样子

$O(n^2)$ 复杂度
第一个递推式变一下就行。
第二个复杂度注意一下边界条件。

以及 $0$~$i-1$ 这个条件没有问题。

本文链接：https://pst.iorinn.moe/archives/sol-bzoj-3670-3620.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆