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
| #include <bits/stdc++.h>
using namespace std;
int d[11000010 << 1], l = 0, r = -1, i, ans, n;
string t;
char s[11000010 << 1];
int main() {
cin >> t;
s[0] = '#';
for (i = 0; i < t.size(); ++i) {
s[(i << 1) + 1] = t[i];
s[(i << 1) + 2] = '#';
}
n = (i << 1) + 3;
for (i = 0; i < n; ++i) {
if (i <= r) {
d[i] = min(d[l + r - i], r - i);
}
while (i - d[i] >= 0 && i + d[i] < n && s[i - d[i]] == s[i + d[i]]) {
++d[i];
}
if (i + d[i] > r) {
l = i - d[i];
r = i + d[i];
}
ans = max(ans, d[i]);
}
cout << ans - 1 << endl;
}
|