ACM模版

描述

题解

先吐槽一下，这个题目搬运工可不走心啊……翻译的有问题，还是看了讨论区才知道题意有问题……

这个题要你求所有前缀回文度的和，这个不难想到，在 macacher 算法中求出来的一个数组中，表示着以某个位置为轴心的回文半径，那么我们完全可以通过这个来判定某一个前缀是否为回文，这样也就能够求出来所有回文前缀。

此时，我们应该仔细分析什么是回文度，其实，回文度是一种递归嵌套关系，他的大小与回文前缀长度并没有特别直接的关系（当然，间接关系还是有的，它限制着回文度的最大值），直接相关的是递归嵌套的层数。那么，我们可以肯定，上述求出来的回文前缀中会存在递归嵌套关系，我们只需要根据这些嵌套关系就可以求出每个前缀的回文度，求和即可。

代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int MAXN = 1e7 + 10;

char A[MAXN];
int B[MAXN];

void Manacher(int len)
{
    int mx = 0, id = 0;
    for (int i = 1; i < len; i++)
    {
        if (i <= mx)
        {
            B[i] = min(B[2 * id - i] , mx - i + 1);
        }
        else
        {
            B[i] = 1;
        }
        while (A[i - B[i]] == A[i + B[i]])
        {
            B[i]++;
        }
        if (i + B[i] - 1 > mx)
        {
            id = i;
            mx = i + B[i] - 1;
        }
    }
}

int main()
{
    char ch;
    int len = 0;
    A[len++] = '$';
    A[len++] = '#';
    while ((ch = getchar()) != '\n' && ch != EOF)
    {
        A[len++] = ch;
        A[len++] = '#';
    }
    A[len] = '\0';

    Manacher(len);

    int pos = 1;
    len /= 2;
    for (int i = 2; i <= len; i++)
    {
        A[pos++] = B[i] == i;
    }

    memset(B, 0, sizeof(B));
    for (int i = 1; i < pos; i++)
    {
        if (A[i])
        {
            B[i] = B[i / 2] + 1;
        }
    }

    int ans = 0;
    for (int i = 1; i < pos; i++)
    {
        ans += B[i];
    }

    cout << ans << endl;

    return 0;
}