Manacher algorithm
February 11, 2025
1 Introduction
Manacher algorithm is designed to solve longest palindrome problems. It uses the symmetry prop-
erty of a palindrome and previous step simultaneously, so become more effective algorithm than
many others, with time complexity 𝑂(𝑛).
[ ]: %load_ext cppsetup
[ ]: %%cpp input
[ ]: %%cpp
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
#define Fast ios_base::sync_with_stdio(false);[Link](NULL);[Link](NULL)
2 Problem
Given string s (the length of s is n), find a longest palindromic substring in s at each position.
3 Solving
3.1 Bruce-Force algorithm
Let 𝑟[𝑖] be a half length of the longest substring with center being element at position 𝑖 in s. The
prolem will be solved, if we fill all element of list 𝑟. We can use two loop to filling list 𝑟. The first
loop (using iterator 𝑖) will be used to iterate all element of s. In the first loop, we will use the
second loop (using iterator 𝑗 beginning from 𝑖 + 1) to check element at position 𝑗 and 𝑖 in s. We
will repeat the second loop until having two different elements, then we update 𝑟[𝑖]. After all, we
repeat the first loop. - Time complexity: 𝑂(𝑛2 ) - Space complexity: 𝑂(𝑛)
3.2 Manacher algorithm
3.2.1 1. Definition and Problem Statement
Let 𝑠[𝛼𝑖 , 𝛽𝑖 ] be the longest substring from position 𝛼 to position 𝛽 in s, with element at position
𝑖 as the center. Moreover, we add extra characters to make all palindromes have an odd length,
1
allowing the algorithm to handle both odd- and even-length cases uniformly. We still use 𝑟[𝑖] from
brute-force expansion.
The problem is to find 𝑟[𝑖] that satisfies:
𝑠[𝑖 − 𝑟[𝑖], 𝑖 − 1] = 𝑠[𝑖 + 1, 𝑖 + 𝑟[𝑖]]
Assume that 𝑟[𝑖 − 1] was found, so we would have:
𝑠[𝛼𝑖−1 , 𝑖 − 2] = 𝑠[𝑖, 𝛽𝑖−1 ]
How does we use 𝑟[𝑖 − 1] to calculate 𝑟[𝑖]?
[ ]: %%cpp
string insert_s(string s){
string t = s + s + "$";
int j = 0;
for(int i = 0; i < [Link](); i++){
if(i % 2 == 0) t[i] = '$';
else{
t[i] = s[j];
j++;
}
}
return t;
}
3.2.2 2. Possible Cases for Position 𝑖
We know that position 𝑖 has two cases:
𝑖 ∈ [𝛼𝑖−1 , 𝛽𝑖−1 ] or 𝛼𝑖−1 < 𝑖 ≤ 𝛽𝑖−1
[
𝑖 ∉ [𝛼𝑖−1 , 𝛽𝑖−1 ] or 𝑖 > 𝛽𝑖−1
3.2.3 3. Case 1: 𝛼𝑖−1 < 𝑖 ≤ 𝛽𝑖−1
Let 𝑗 = 𝛼𝑖−1 + 𝛽𝑖−1 − 𝑖, that will satisfy:
𝑆[𝑗, 𝑗] = 𝑆[𝑖, 𝑖]
3.1. When 𝛽𝑗 ≤ 𝛽𝑖−1 If 𝑆[𝛼𝑖−1 , 𝛽𝑖−1 ] is a palindromic substring, then:
𝑆[𝛼𝑗 , 𝑗 − 1] = 𝑆[𝑖 + 1, 𝑖 + 𝑟[𝑗]]⎫
} ⇒ 𝑆[𝑖 − 𝑟[𝑗], 𝑖 − 1] = 𝑆[𝑖 + 1, 𝑖 + 𝑟[𝑗]]
𝑆[𝑗 + 1, 𝛽𝑗 ] = 𝑆[𝑖 − 𝑟[𝑗], 𝑖 − 1]
⎬ ⇒ 𝑟[𝑖] = 𝑟[𝑗]
𝑆[𝛼𝑗 , 𝑗 − 1] = 𝑆[𝑗 + 1, 𝛽𝑗 ] }
⎭
3.2. Otherwise
𝑆[𝛼𝑖−1 , 𝑗 − 1] = 𝑆[𝑗 + 1, 2𝑗 + 𝛼𝑖−1 ] ⎫
} ⇒ 𝑆[𝑖 − 𝑗 + 𝛼𝑖−1 , 𝑗 − 1] = 𝑆[𝑖 + 1, 𝑖 + 𝑗 − 𝛼𝑖−1 ]
𝑆[𝛼𝑖−1 , 𝑗 − 1] = 𝑆[𝑖 + 1, 𝑖 + 𝑗 − 𝛼𝑖−1 ]
⎬ ⇒ 𝑟[𝑖] = 𝛽𝑖−1 − 𝑖
𝑆[𝑗 + 1, 2𝑗 − 𝛼𝑖−1 ] = 𝑆[𝑖 − 𝑗 + 𝛼𝑖−1 , 𝑖 − 1] }
⎭
2
3.3. Expand the range of 𝑠[𝛼𝑖 , 𝛽𝑖 ]
Because 𝑟[𝑖] is maximum, we must check if 𝑠[𝑖 − 𝑟[𝑖] − 1, 𝑖 −𝑟[𝑖] − 1] = 𝑠[𝑖 + 𝑟[𝑖] + 1, 𝑖 + 𝑟[𝑖] + 1].
If it true, we update 𝑟[𝑖].
3.2.4 4. Case 2: 𝑖 > 𝛽𝑖−1
In this case, we can’t link 𝑟[𝑖] with 𝑟[𝑖 − 1] because we don’t know any element over position 𝛽𝑖−1 .
Therefore, we must use Bruce-Force to find 𝑟[𝑖] and 𝑠[𝛼𝑖 , 𝛽𝑖 ].
[ ]: %%cpp
void fill_r(string s, int *&r){
int alp = 0, bet = 0;
r[0] = 0;
for(int i = 1; i < [Link](); i++){
int j = alp + bet - i;
if(j > 0 && bet >= j + r[j]) r[i] = min(r[j], bet - i);
if(i > bet) r[i] = 0;
alp = i - r[i] - 1;
bet = i + r[i] + 1;
while(alp >= 0 && bet < [Link]() && s[alp] == s[bet]){
r[i]++;
alp --;
bet ++;
}
alp++;
bet--;
}
}
[ ]: %%cpp
signed main(){
int n;
string s;
cin >> n >> s;
s = insert_s(s);
int *r = new int[[Link]() + 5];
fill_r(s, r);
int res = 0;
for(int i = 0; i < [Link](); i++){
res = max(res, r[i]);
}
cout << res;
}