AC. 梦想

frank_c1

[NOI 2016] 优秀的拆分

发布于2016年08月06日 | 暂无评论 | 812阅读 | 后缀数组

题目描述

如果一个字符串可以被拆分为AABB的形式,其中AB是任意非空字符串,则我们称该字符串的这种拆分是优秀的。

例如,对于字符串aabaabaa,如果令A=aabB=a,我们就找到了这个字符串拆分成AABB的一种方式。

一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分。比如我们令A=aB=baa,也可以用AABB表示出上述字符串;但是,字符串abaabaa就没有优秀的拆分。

现在给出一个长度为n的字符串S,我们需要求出,在它所有子串的所有拆分方式中,优秀拆分的总个数。这里的子串是指字符串中连续的一段。

以下事项需要注意:

出现在不同位置的相同子串,我们认为是不同的子串,它们的优秀拆分均会被记入答案。

在一个拆分中,允许出现A=B。例如cccc存在拆分A=B=c

字符串本身也是它的一个子串。

输入格式

每个输入文件包含多组数据。输入文件的第一行只有一个整数T,表示数据的组数。保证1 \le T \le 10

接下来T行,每行包含一个仅由英文小写字母构成的字符串S,意义如题所述。

1 \le n \le 30000

输出格式

输出T行,每行包含一个整数,表示字符串S所有子串的所有拆分中,总共有多少个是优秀的拆分。

题目解析

同步赛考场上看到这题的部分分吓呆了。暴力95分这是什么意思?写发哈希,也不想去想正解了。

不过正解的思想还是不错的。

首先,我们发现只要找出所有形如AA的串即可。设有A_i个这样的串结束位置是i,有B_i个这样的串开始位置是i,则

ans = \sum_{i=1} ^ {n-1} {A_i B_{i+1}}

我们考虑怎样快速求出AB

我们枚举AA串中A的长度L。在原串上,我们每隔L设置一个关键点,可以发现,若A的长度为LAA必定恰好经过某两个相邻的关键点。于是我们可以枚举AA经过的关键点。

考虑两个相邻的关键点a,b,有b = a + L,我们求出a,b的最长公共前缀p和最长公共后缀s。若p + s \gt LAA串就一定存在,且可行的开始位置区间是[a - s + 1, a + p - L],可行的结束位置区间是[b - s + L, b + p - 1]。由于每次是对一段区间加1,差分一波即可。

根据调和级数,枚举的时间复杂度

T(n) = \sum_{i=1} ^ {n} {O(\frac{n} {i})} = O(n \log n)

最长公共前后缀可用后缀数组实现。总时间复杂度O(n \log n)