-
Notifications
You must be signed in to change notification settings - Fork 1
/
P3805.c
36 lines (32 loc) · 832 Bytes
/
P3805.c
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
32
33
34
35
36
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 11000007
#define N2 (N<<1)
char raw[N], s[N2];
int p[N2];
static inline int min(int a, int b) { return a < b ? a : b; }
int main() {
int n, i, j, left, right, ans;
scanf("%s", raw);
n = strlen(raw);
s[0] = '$';
for (i = 0, j = 1; i < n; i++) {
s[j++] = raw[i];
s[j++] = '$';
}
s[j] = 0;
n = j;
left = 0, right = -1, ans = 0;
for (i = 0; i < n; i++) {
p[i] = (i >= right ? 0 : min(p[left + right - i], right - i));
while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n && s[i - p[i] - 1] == s[i + p[i] + 1]) p[i]++;
if (i + p[i] > right) {
left = i - p[i];
right = i + p[i];
}
if (p[i] > ans) ans = p[i];
}
printf("%d", ans);
exit(0);
}