BZOJ3670/3620 [NOI2014]动物园 / 似乎在梦中见过的样子
空気浮遊
2018年08月14日
后一题让我重新审视了一下前一道题我是怎么 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$ 这个条件没有问题。