Watware @ 2021-12-31 17:33:44
manacher算法只有88pts,最后一个点WA掉,不知道为什么
#include <bits/stdc++.h>
using namespace std;
const int M = 15010000;
char str[M];
int l, sz, p[M], ans = 0, mid;
int main()
{
scanf("%d", &l);
char c = getchar();
while (!isalpha(c))
c = getchar();
str[1] = '[';
for (int i = 1; i <= l; i++)
{
str[i << 1] = c;
str[i << 1 | 1] = '|';
c = getchar();
}
str[l + 1 << 1] = ']';
sz = l << 1 | 1;
for (int c = 0, mx = 0, i = 1; i <= sz; i++)
{
p[i] = 1;
if (i <= mx)
p[i] = min(p[2 * c - i], mx - i);
if (str[i] != '|')
while (str[i - p[i]] == str[i + p[i]])
p[i]++;
else
while (str[i - p[i]] == str[i + p[i]])
{
if ((p[i] & 2) && p[i] >= 3)
{
mid = 2 * i - p[i] - 1 >> 1;
if (p[mid] >= i - mid)
ans = max(ans, p[i] + 1);
}
p[i]++;
}
if (i + p[i] > mx)
mx = i + p[i], c = i;
}
printf("%d", ans);
return 0;
}