[Link] https://www.acmicpc.net/problem/13275
Manacher Algorithm
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
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int INF = 987654321;
int main() {
string s;
cin >> s;
int len = s.size();
vector<int> odd;
vector<int> even;
odd.resize(len);
even.resize(len);
int oddMax = -1, evenMax = -1;
//even[i] : i - 1 == i
int l_odd = 0, r_odd = -1;
int l_even = 0, r_even = -1;
for(int i = 0; i < len; i++) {
odd[i] = i <= r_odd ? min(r_odd - i + 1, odd[l_odd + r_odd - i]) : 1;
even[i] = i <= r_even ? min(r_even - i + 1, even[l_even + r_even - i + 1]) : 0;
while(
0 <= i - odd[i] &&
i + odd[i] < len &&
s[i - odd[i]] == s[i + odd[i]]
) odd[i]++;
while(
0 <= i - 1 - even[i] &&
i + even[i] < len &&
s[i - 1 - even[i]] == s[i + even[i]]
) even[i]++;
oddMax = max(oddMax, odd[i]);
evenMax = max(evenMax, even[i]);
if(i + odd[i] - 1 > r_odd) {
r_odd = i + odd[i] - 1;
l_odd = i - odd[i] + 1;
}
if(i + even[i] - 1 > r_even) {
r_even = i + even[i] - 1;
l_even = i - even[i];
}
}
cout << max(2 * evenMax, 2 * oddMax - 1);
return 0;
}