Manacher Palindromes Algorithm
The Manacher Palindromes Algorithm is an efficient linear time algorithm designed to find the longest palindromic substring within a given string. A palindrome is a sequence of characters that reads the same forward and backward, such as "abccba" or "madam". Developed by Glenn Manacher in the 1970s, this algorithm outperforms other more naive approaches, which often have quadratic time complexity. The crux of the algorithm is its ability to re-use previously computed information about palindromes centered at various positions in the string, which allows it to avoid redundant computations and achieve linear time complexity.
The Manacher Palindromes Algorithm works by first transforming the input string to a modified string where each character is separated by a special character, typically '#', and bookended by two other unique characters, usually '@' and '$'. This transformation helps to handle even-length palindromes uniformly with odd-length ones. The algorithm then iterates through the modified string, maintaining a "center" and "right boundary" for the palindrome it's currently working with. For each position in the modified string, it computes a "palindrome radius" based on previously computed palindrome radii and updates the center and right boundary as needed. The algorithm also keeps track of the longest palindrome found so far. Once the iteration is complete, the longest palindromic substring can be extracted from the longest palindrome radius and its corresponding center in the modified string.
/****************************************************************************
Manacher's algorithm for finding all subpalindromes in the string.
Based on problem L from here: http://codeforces.ru/gym/100133
****************************************************************************/
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
using namespace std;
const int MAXN = 105000;
string s;
int n;
int odd[MAXN], even[MAXN];
int l, r;
long long ans;
int main() {
assert(freopen("palindrome.in","r",stdin));
assert(freopen("palindrome.out","w",stdout));
getline(cin, s);
n = (int) s.length();
// Odd case
l = r = -1;
for (int i = 0; i < n; i++) {
int cur = 1;
if (i < r)
cur = min(r - i + 1, odd[l + r - i]);
while (i + cur < n && i - cur >= 0 && s[i - cur] == s[i + cur])
cur++;
odd[i] = cur;
if (i + cur - 1 > r) {
l = i - cur + 1;
r = i + cur - 1;
}
}
// Even case
l = r = -1;
for (int i = 0; i < n; i++) {
int cur = 0;
if (i < r)
cur = min(r - i + 1, even[l + r - i + 1]);
while (i + cur < n && i - 1 - cur >= 0 && s[i - 1 - cur] == s[i + cur])
cur++;
even[i] = cur;
if (i + cur - 1 > r) {
l = i - cur;
r = i + cur - 1;
}
}
for (int i = 0; i < n; i++) {
if (odd[i] > 1) {
ans += odd[i] - 1;
}
if (even[i])
ans += even[i];
}
cout << ans << endl;
return 0;
}
