A M形字符串

题号：NC220345
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给一个长度为n的字符串(1<=n<=200000),他只包含小写字母

找到这个字符串多少个前缀是M形字符串.

M形字符串定义如下:

他由两个相同的回文串拼接而来,第一个回文串的结尾字符和第二个字符串的开始字符可以重叠,也就是以下都是M形字符串.

abccbaabccba(由abccba+abccba组成)

abcbaabcba(有abcba+abcba组成)

abccbabccba(由abccba+abccba组成组成,但是中间的1是共用的)

a(一个单独字符也算)

输入一行,一个长度为n的字符串

输出这个字符串有多少个前缀是M形字符串

示例1

复制

abababcabcba

复制

a是M形串

ababa是M形串

示例2

复制

abccbaabccba

复制

a是M形串

abccbaabccba是M形串