占位符
作者:
LOSTDLL
,
2024-05-08 13:58:01
,
所有人可见
,
阅读 3
#include <iostream>
#include <cstring>
#include <algorithm>
const int N = 2e7 + 10;
char a[N], b[N];
int p[N];
int len, n;
void init()
{
b[len ++] = '$', b[len ++] = '#';
for(int i = 0; i < n; i ++)
{
b[len ++] = a[i];
b[len ++] = '#';
}
b[len ++] = '^';
n = len;
return;
}
void manacher() // 求最长回文串
{
int mr = 0, mid = 0;
for(int i = 0; i < n; i ++)
{
if(i < mr) p[i] = std :: min(p[2 * mid - i], mr - i);
else p[i] = 1;
while(b[i - p[i]] == b[i + p[i]]) p[i] ++;
if(i + p[i] > mr)
{
mr = i + p[i];
mid = i;
}
}
}
int main()
{
std :: cin >> a;
n = strlen(a);
init();
manacher();
int res = 0;
for(int i = 0; i < n; i ++) res = std :: max(res, p[i]);
std :: cout << res - 1 << "\n";
return 0;
}