#P18695. Repetitive String Invention
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。
因此总共有九种方法。
输入格式
输入只有一行,包含字符串 ,满足 ,每个字符都在 a 到 z 之间。这就是 Lulu 的原字符串。
输出格式
输出一个整数,表示按原顺序选择两个非空、不重叠子串,并使拼接结果为重复字符串的方法数。
样例 1 输入
aaaa
样例 1 输出
9
样例 2 输入
axabxbcxcdxd
样例 2 输出
22