#P18695. Repetitive String Invention

    ID: 18031 传统题 2000ms 2048MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-最长公共前缀枚举中间点树状数组对称性分析

Repetitive String Invention

Repetitive String Invention

Lulu 有一个只包含小写英文字母的字符串。她想用它得到一个“重复字符串”:这种字符串的长度为偶数,而且前一半与后一半完全相同。例如,lulu、abcabc 和 xx 都是重复字符串,而 xyx 和 abac 不是。

Lulu 可以从原字符串中选择两个非空、互不重叠的子串,并按照它们在原字符串中出现的先后顺序拼接。两段可以紧邻,也可以隔着一些没有选取的字符;它们的长度不要求相等。

有多少种选择两个子串的方法,能使拼接结果成为重复字符串?只要至少一个所选子串在原字符串中的位置不同,就视为不同的方法。这里统计的是所选的两段及其位置,不是不同的拼接结果字符串个数。

例如,对于 aaaa:

  • 选择两个单独的 a 得到 aa,共有六种位置组合:第 1、2 个,第 1、3 个,第 1、4 个,第 2、3 个,第 2、4 个,以及第 3、4 个字符。
  • 得到 aaaa 有三种分法:a + aaa、aa + aa、aaa + a。

因此总共有九种方法。

输入格式

输入只有一行,包含字符串 ss,满足 1≤∣s∣≤8001\le |s|\le800,每个字符都在 a 到 z 之间。这就是 Lulu 的原字符串。

输出格式

输出一个整数,表示按原顺序选择两个非空、不重叠子串,并使拼接结果为重复字符串的方法数。

样例 1 输入

aaaa

样例 1 输出

9

样例 2 输入

axabxbcxcdxd

样例 2 输出

22