1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include <cstdio>
#include <algorithm>
using namespace std;
const int N = 3e7 + 10;
char s[N];
int n, d[N];
void init()
{
s[n++] = '$', s[n++] = '#';
char c = getchar();
while (c < 'a' || c > 'z') c = getchar();
while (c >= 'a' && c <= 'z')
s[n++] = c, s[n++] = '#', c = getchar();
s[n++] = '^';
}
int main()
{
init();
for (int i = 0, t = -1; i < n; ++i)
{
d[i] = 1;
if (~t && i <= t + d[t] - 1) d[i] = min(d[t * 2 - i], d[t] + t - i);
while (i - d[i] >= 0 && i + d[i] < n && s[i - d[i]] == s[i + d[i]]) ++d[i];
if (i + d[i] > t + d[t]) t = i;
}
int res = 2;
for (int i = 0; i < n; i++)
res = max(res, d[i]);
printf("%d", res - 1);
return 0;
}
|