样例输入

abbab

样例输出

          8

manacher算法，可以直接求出
i 枚举中心位置，p[i] 记录i下标为中心的最长回文串半径，
id记录已匹配的回文串中点下标，mx记录已匹配的回文串的右边界下标+1

#include <bits/stdc++.h>

using namespace std;

#define LL long long

#define MOD 1000000007

#define MX 800050

int len;

char temp[MX];

char str[MX*];

int p[MX*];

LL ans;

void Init()

{

    len = , ans = ;

    str[len++]='!';

    str[len++]='#';

    int t = strlen(temp);

    for (int i=;i<t;i++)

    {

        str[len++]=temp[i];

        str[len++]='#';

    }

    memset(p,,sizeof(p));

}

void Manacher()

{

    int mx = , id =;

    for (int i=;i<len;i++)

    {

        p[i] = mx>i ? min(p[*id-i],mx-i):;

        while (i-p[i]>= && str[i+p[i]]==str[i-p[i]]) p[i]++;

        ans+=p[i]/;

        if (i+p[i]>mx)

        {

            mx = i+p[i];

            id = i;

        }

    }

}

int main()

{

    while (scanf("%s",temp)!=EOF)

    {

        Init();

        Manacher();

        printf("%lld\n",ans);

    }

    return ;

}