迷之回文

题目描述

FF 最近喜欢上了回文串，比如 aa ， aba 都是回文串，今天 FF 有了一个奇葩的想法。

对于给定的一个字符串S(仅有小写英文字母组成，|S| <= 100000)，FF想知道S的前缀中有多少个是回文串。

如，ababa，前缀”a”,”aba”,”ababa”都是回文串。

输入

  多组输入。每组数据一个字符串 S 。

输出

  对于每组数据输出一个数代表答案。

示例输入

ababaabcde

示例输出

31

#include
    
     #include
     
      long long a[100010], b[100010], p;char c[100010];#define t 17int main() {    int i, n, ans=0;    while(scanf("%s", c+1) != EOF) {        n = strlen(c+1);        for(a[0]=0,i=1; i<=n; i++)            a[i] = a[i-1]*t + c[i]-'a';        for(b[0]=0,p=1,i=1; i<=n; i++)            b[i] = b[i-1] + (c[i]-'a')*p, p*=t;        int ans = 0;        for(i=1; i<=n; i++)            if(a[i] == b[i])                ans++;        printf("%d\n", ans);    }    return 0;}