Manacher's Algorithm
Manacher's Algorithm is used for finding sub-palindromes in a given string in linear time. More formally, the problem statement is as follows: Given a string with length . Find all the pairs such that substring is a palindrome. String is a palindrome when ( is a reversed string for ).
A straightforward solution can be iterating through each character of the given string and treating it as a center of a palindrome, i.e. looking at neighboring characters and increasing positions by as long as it's possible, comparing a pair of corresponding characters each time. To avoid the overflow and passing left and right borders, we can add terminal characters to indicate those borders.
The implementation of the trivial algorithm is:
Terminal characters $ and ^ were used to avoid dealing with ends of the string separately.
Let denote the odd-length palindromes centered at . Let be the borders of the rightmost found (sub-)palindrome (i. e. the current rightmost (sub-)palindrome is ). Initially, , which is an empty string.
Next, we want to calculate , so:
To handle such situations correctly, we should restrict the length of our palindrome for now, i. e. have , . After this we'll run the simple approach described above. which will try to increase while it's possible.
Illustration of this case (the palindrome with center is restricted to fit the "outer" palindrome):
It is shown in the illustration that though the palindrome with center could be larger and go outside the "outer" palindrome, but with as the center we can use only the part that entirely fits into the "outer" palindrome. But the answer for the position ( ) can be much bigger than this part, so next we'll run our trivial algorithm that will try to grow it outside our "outer" palindrome, i. e. to the region "try moving here". As a reminder, to work correctly we should update the values after calculating each .
Implementation for odd length Manacher's algorithm:
While we could use the above approach and modify it to consider two characters as centers of an even-length string, it is possible to reduce the whole problem to the case when we only deal with the palindromes of odd length. To do this, we can put an additional character between each letter in the string and also in the beginning and the end of the string. This would still maintain the properties of existing palindromes and make a string odd-length:
Here, and where denotes the Manacher array for odd-length palindromes in -joined string, while and correspond to the arrays defined above in the initial string.
The algorithm with the string adjustment can be implemented as follows:
vector<int> simpleManacher(string s) {
int n = s.size();
s = "$" + s + "^";
vector<int> p(n + 2);
for(int i = 1; i <= n; i++) {
while(s[i - p[i]] == s[i + p[i]]) {
p[i]++;
}
}
return vector<int>(begin(p) + 1, end(p) - 1);
}
vector<int> oddLengthManacher(string s) {
int n = s.size();
s = "$" + s + "^";
vector<int> p(n + 2);
int l = 1, r = 1;
for(int i = 1; i <= n; i++) {
p[i] = max(0, min(r - i, p[l + (r - i)]));
while(s[i - p[i]] == s[i + p[i]]) {
p[i]++;
}
if(i + p[i] > r) {
l = i - p[i], r = i + p[i];
}
}
return vector<int>(begin(p) + 1, end(p) - 1);
}
vector<int> adjustedManacher(string s) {
string t;
for(auto c: s) {
t += string("#") + c;
}
auto res = oddLengthManacher(t + "#");
return vector<int>(begin(res) + 1, end(res) - 1);
}