题解 P1117 【[NOI2016]优秀的拆分 】

### Description 求对每一个连续字串将它切割成形如 AABB 的形式的方案数之和 ### Solution 显然 AABB 是由两个 AA 串拼起来的 考虑维护两个数组 a[i] 和 b[i] ，其中 a[i] 表示以 $i$ 结尾有多少个 AA 串，b[i] 表示以 $i$ 开头有多少个 AA 串 最后答案就是 $\sum \limits _{i=1}^{n-1}a[i]b[i+1]$ （就是两个串拼起来） 如何求 a[i] 和 b[i] 呢？ 首先有一个非常显然的 n^2 哈希做法（对于每一个 $i$ 用 $j$ 扫一遍用哈希判断有几个 AA 串），有 95 分！ 如何拿到最后的 5 分呢？考虑枚举一个 Len ，然后对于每个点求出他是否是一个 2 * Len 的 AA 串的开头 / 结尾。 我们每隔 Len 放一个点，这样每一个 长度为 2 * Len 的 AA 串都至少会经过两个相邻的点。 所以再转换为每两个相邻的点会对 a, b 产生多少贡献。 先求出这对相邻点所代表的前缀的最长公共后缀 LCS 和 所代表的后缀的最长公共前缀 LCP 如果 LCP + LCS < Len 就下面这种情况：  其中两个红线是关键点（相距为 Len），蓝线是LCS，绿线是LCP，LCP+LCS < Len 则有  这条紫线就是第一个可能满足条件的 AA 串 但此时我们会发现下图  其中两个红色荧光笔的部分在 AA 串中是对应的，但他们至少有一个位置并不相同 （不然LCP可以再长） 所以此时不会有任意一个长度为 2 * Len 的 AA 串满足条件。 如果 LCP + LCS >= Len 就有下面这种情况  此时中间必然就没有空隙。可以发现：  粉色的是第一个 AA 串，可以发现它是可以分成两个相同的 A 串的（可以理解成中间没有缝隙了所以就没有不一样的了） 然后这个 AA 串可以一直往后滑动，每滑动一个位置都可以形成一个新的 AA 串知道 AA 串的后端点滑动到最右边的绿色端点。也就是滑动到棕色 AA 串 此时可以发现，每一个存在于红色荧光部分的点都可以作为一个新的 AA 串的开头 同理，每一个再绿色荧光笔的点可以作为一个新的 AA 串的结尾。 于是就将红色荧光笔的区间的 b 加上 1，绿色的 a 加上 1，就大功告成。 如何实现这个过程呢？复杂度是什么呢？ 1. 枚举 Len ，每隔 Len 设置关键点：这个的复杂度是调和级数 $O(n \log n)$ 2. 求 后缀LCP，前缀LCS：使用后缀数组 + st 表 做到 O(1) 查询 3. 区间加上 1 ： 差分维护就可以了。 至此，此题完结 ### Code [看代码戳这里](https://www.cnblogs.com/acfunction/p/10087144.html)