-
Notifications
You must be signed in to change notification settings - Fork 0
/
manachers_algorithm.cpp
50 lines (50 loc) · 1.26 KB
/
manachers_algorithm.cpp
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
50
// Manacher's Algorithm
// Find all palindromes in string in O(N)
// BOJ 14444 AC Code
// https://www.acmicpc.net/problem/14444
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (x).size()
int n; // n: length of string
string s;
vector<int> p; // p[i]: the radius of the palindrome at the current position i
void manacher() {
// Preprocessing for determining even-length pelindromes
n = sz(s);
s.resize(n << 1 | 1);
p.resize(n << 1 | 1);
for (int i = n - 1; i >= 0; i--) {
s[i << 1 | 1] = s[i];
s[i << 1] = '#';
}
n <<= 1;
s[n++] = '#';
// Processing
int r = -1, c = -1;
// r: end of palindrome
// c: center of palindrome
for (int i = 0; i < n; i++) {
if (i <= r) p[i] = min(r - i, p[c * 2 - i]);
else p[i] = 0;
while (1) {
if (i - p[i] - 1 < 0 || i + p[i] + 1 >= n) break;
if (s[i + p[i] + 1] != s[i - p[i] - 1]) break;
p[i]++;
}
if (i + p[i] > r) {
r = i + p[i], c = i;
}
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> s;
manacher();
// Get answer
int ans = 0;
for (int i = 0; i < n; i++) {
ans = max(ans, p[i]);
}
cout << ans;
}