Manacher

Algorithm

Step 1. Inserting special characters

Assume the original string is s, and the string after insertion is t.

We insert special characters into s so as to avoid handling palindromes of odd length and even length separately.

We insert * around every character, prepend a ^ and append a $ to the string.

For example:

// Odd case
"aba" // the palindrome was of length 3
// becomes
"^*a*b*a*$" // the palindrome is of length 7
//   ^
//   this b is still the center.


// Even case
"abba" // the palindrome was of length 4
// becomes
"^*a*b*b*a*$" // the palindrome is of length 9
//    ^
//    this * becomes the new center

How to convert the indexes between s and t?

      0 1 2
s =   a b c
    012345678
t = ^*a*b*c*$

0 -> 2
1 -> 4
2 -> 6

(indexInS + 1) * 2 = indexInT

indexInT / 2 - 1 = indexInS

We only need to consider the indexes in t in range [2, s.size() * 2], which corresponds to [0, s.size()-1] in s.

Step 2. Calculate r array

Let r[i] be the number of palindromes centered at t[i] (aka. the radius of the longest palindrome centered at t[i]).

So we have:

• the longest palindrome centered at t[i] is t[i-r[i]+1 .. i+r[i]-1].

• For any k < r[i], substring t[i-k .. i+k] is a palindrome.

• For any k >= r[i], substring t[i-k .. i+k] is not a palindrome.

Example:

     0123456789012
t = "^*a*b*c*b*d*$"
        ^  ^  ^

For center t[6] = 'c', we have r[6] = 4:

• The longest palindrome centered at t[6] is t[3 .. 9] = "*b*c*b*"

• For any k < 4, substring t[6-k .. 6+k] is a palindrome. E.g. for k = 2, t[4 .. 8] = "b*c*b" is a palindrome.

• For any k >= 4, substring t[6-k .. 6+k] is not a palindrome. E.g. for k = 4, t[2 .. 10] = "a*b*c*b*d" is not a palindrome.

To calculate r[i] efficiently, we need to leverage the computed r[j] (j < i) values.

Let j < i be the center with the furthest reach j + r[j].

For i-1, since r[i-1] >= 1, the corresponding reach i-1 + r[i-1] is at least i.

So, j + r[j] must be >= i.

Case 1: j + r[j] == i:

Since the palindrome t[j-r[j]+1 .. j+r[j]-1] doesn't cover t[i], we have no information to leverage, and have to expand from t[i] in a brute force way.

Example:

     01234567890
t = "^*a*b*c*b*$"
        [^]^
         j i

For t[6] = 'c', the corresponding j could be 4 and r[j] = 2. Since j + r[j] == i == 6, we expand at t[6] brute-forcely. And we will get r[6] = 4.

Since i + r[i] = 6 + 4 = 10 > j + r[j] = 6, we will make i = 6 the new center j.

Case 2: j + r[j] > i:

Now we can leverage some symmetry information.

Assume the symmetry point of i relative to j is k = 2*j-i. We need to consider 3 subcases about whether the range (j-r[j], j+r[j]) covers (k-r[k], k+r[k]).

Case 2a: k-r[k] > j-r[j]:

Example:

     012345678901234
t = "$*a*b*c*b*a*d*$"
         ^ ^ ^
         k j i
r =    212161?
      [    j    ]
        [k] [i]

In this case, we must have r[i] = r[k] = r[2*j-i] due to symmetry.

Case 2b: k-r[k] < j-r[j]:

Example:

     01234567890123456789012
t = "^*c*a*a*c*c*c*a*a*d*b*$"
          ^    ^    ^
          k    j    i
r =    2125212383212?
        [      j      ]
      [   k   ]          // not all this range for `k` can be symmetrised.
        [ k ]     [ i ]  // we can only symmetrise the part covered by the range for `j`

Since k-r[k] < j-r[j], not the entire range for k can be symmetrised relative to j. We can only symmetrise the range [j-r[j]+1, 2*k-j+r[j]-1]. So r[i] is at least k - (j-r[j]+1) + 1 = k-j+r[j] = j+r[j]-i.

Assume:

• the range for j is surrounded by index p and s.

• p and q are symmetric relative to k.

• r and s are symmetric relative to i.

       p[      j      ]s
       p[ k ]q   r[ i ]s

We know:

• t[p] != t[s] and t[q] == t[r] because of r[j].

• t[p] == t[q] because of r[k].

So, t[p] == t[q] == t[r] != t[s]. Thus, r[i] is exactly j+r[j]-i.

Case 2c: k-r[k] == j-r[j]:

Example:

     01234567890123456789012
t = "^*d*a*a*c*c*c*a*a*c*b*$"
          ^    ^    ^
          k    j    i
r =    2123212383212?
       p[      j      ]s
       p[ k ]q   r[ i ]s

This is similar to case 2b that we know r[i] is at least j+r[j]-i, with the exception that t[p] != t[q] now.

Given t[p] != t[s], t[q] == t[r] and t[p] != t[q], we can't know whether t[r] == t[s] or not.

So, we have to do brute force expansion with r[i] being at least j+r[j]-i.

Summary of the cases:

• Case 1: j + r[j] == i, we do brute force expansion starting from r[i] = 1.

• Case 2: j + r[j] > i.

  • Case 2a: k-r[k] > j-r[j], we have r[i] = r[k] = r[2*j-i] < j+r[j]-i

  • Case 2b: k-r[k] < j-r[j], we have r[i] = j+r[j]-i < r[k].

  • Case 2c: k-r[k] == j-r[j], we do brute force expansion starting from r[i] = j+r[j]-i = r[k].

Note that for the 3 subcases in case 2, r[i] is either exactly or at least the minimum of r[2*j-i] and j+r[j]-i.

Merging the cases:

We don't need to implement these cases separately. Instead, we use the following implementation to cover all the cases.

vector<int> r(M); // `M` is the length of `t`.
r[1] = 1;
int j = 1; 
for (int i = 2; i <= 2 * N; ++i) {
    // The current radius `cur` is `r[i]`.
    // For case 1, `r[i]` starts from 1.
    // For case 2, `r[i]` starts from `min(r[2*j-i], j+r[j]-i)` which satisfies all the 3 subcases.
    int cur = j + r[j] > i ? min(r[2 * j - i], j + r[j] - i) : 1;
    while (t[i - cur] == t[i + cur]) ++cur; // expanding the current radius
    if (i + cur > j + r[j]) j = i; // if `i` has further reach, make `i` the new `j`.
    r[i] = cur;
}

Step 3. Get the longest palindromic substrings in s

Get the length:

The length of the longest palindrome centering at t[i] is i+r[i]-(i-r[i])-1 = 2*r[i]-1.

The edges of this palindrome must be *. The number of * must be 1 plus the number of valid characters.

Thus, the length of the longest palindrome corresponding to r[i] must be r[i]-1.

Get the starting index:

The longest palindrome centering at t[i] starts at index i - floor((2*r[i] - 1) / 2). Since 2*r[i]-1 must be an odd number, i - floor((2*r[i] - 1) / 2) = i - (2*r[i] - 2) / 2 = i - r[i] + 1.

Since the palindrome must start with *, the first valid character starts at i - r[i] + 2.

Based on the aforementioned equation indexInT / 2 - 1 = indexInS, the palindrome starts at (i - r[i] + 2) / 2 - 1 = (i - r[i]) / 2 in s.

Implementation

// OJ: https://leetcode.com/problems/longest-palindromic-substring/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    string longestPalindrome(string s) {
        string t = "^*";
        for (char c : s) {
            t += c;
            t += '*';
        }
        t += '$'; // inflating the `s` ( example: "abc" becomes "^*a*b*c*$" )

        int N = s.size(), M = t.size(), j = 1; // `j` is the index with the furthest reach `j + r[j]`
        vector<int> r(M, 1); // `r[i]` is the number of palindromes with `t[i]` as the center (aka. the radius of the longest palindrome centered at `t[i]`)
        for (int i = 2; i <= 2 * N; ++i) {
            int cur = j + r[j] > i ? min(r[2 * j - i], j + r[j] - i) : 1; // `k=2*j-i` is the symmetry index of `i` relative to `j`. `j+r[j]-i` is the minimal radius of `i` when `k`'s radius touches or goes out of `j`'s radius.
            while (t[i - cur] == t[i + cur]) ++cur; // expanding the current radius
            if (i + cur > j + r[j]) j = i; // if the current reach is greater than the old reach, update `j`
            r[i] = cur;
        }

        int len = 1, start = 0;
        for (int i = 2; i <= 2 * N; ++i) {
            if (r[i] - 1 > len) {
                len = r[i] - 1; // the corresponding length is `r[i] - 1`
                start = (i - r[i]) / 2; // the corresponding start is `(i - r[i]) / 2`
            }
        }
        return s.substr(start, len);
    }
};

Time Complexity

It seems like that we might do brute force expansion at every i so the time complexity is O(N^2), but actually we won't do that many expansions.

Whenever we successfully do an expansion with k steps, we will update j increasing j + r[j] by k. So, the amount of expansion is the same as the increase to j + r[j]. Since j + r[j] at most increases by t.size(), the amount of expansion we did must be at most t.size() times, which takes O(N) time.

Thus, the overall time complexity of Manacher is O(N).

Reference

• [Algorithm][018] 最长回文子串 Manacher [OTTFF]

Problems

• 5. Longest Palindromic Substring (Medium)

• 647. Palindromic Substrings (Medium)