描述
题解
先吐槽一下,这个题目搬运工可不走心啊……翻译的有问题,还是看了讨论区才知道题意有问题……
这个题要你求所有前缀回文度的和,这个不难想到,在 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;
}