Manacher

Description

Given a string $s$ of length $n$, find all pairs $(i, j)$ such that the substring $s[i \dots j]$ is a palindrome. A string $t$ is a palindrome when $t = t_{\text{rev}}$ ($t_{\text{rev}}$ is the reverse of $t$).

Explanation

There may be $O(n^2)$ palindromic substrings in the worst case, so at first glance it seems that this problem has no linear-time algorithm.

However, information about palindromic substrings can be expressed in a more compact way: for every position $i = 0 \dots n - 1$, we determine the values $d_1[i]$ and $d_2[i]$. They represent, respectively, the number of odd-length and even-length palindromic substrings centered at position $i$. Equivalently, they represent the radius of the longest palindrome centered at position $i$ (the radius lengths $d_1[i]$ and $d_2[i]$ are both the number of characters from position $i$ through the rightmost position of the palindrome).

For example, the string $s = \mathtt{abababc}$ has three odd-length palindromic substrings centered at $s[3] = b$. The longest palindrome has radius $3$, so $d_1[3] = 3$:

The string $s = \mathtt{cbaabd}$ has two even-length palindromic substrings centered at $s[3] = a$. The longest palindrome has radius $2$, so $d_2[3] = 2$:

The key idea is that if we have a palindrome of length $l$ centered at some position $i$, then we also have palindromes of lengths $l - 2$, $l - 4$, and so on centered at $i$. Thus, the two arrays $d_1[i]$ and $d_2[i]$ contain enough information about all palindromic substrings of the string.

A surprising fact is that there is a sufficiently simple linear-time algorithm for computing the two arrays of palindromic properties, $d_1[]$ and $d_2[]$. In this article, we describe the algorithm in detail.

Solution

In general, there are several ways to solve this problem: using string hashing, it can be solved in $O(n \log n)$ time, while using a suffix array and fast LCA, it can be solved in $O(n)$ time.

However, the algorithm described here is overwhelmingly simple and has smaller constants in both time and space complexity. The algorithm was proposed by Glenn K. Manacher in 1975.

Naive algorithm

To avoid ambiguity in what follows, let us clarify what we mean by the “naive algorithm.”

The algorithm works as follows: for each center position $i$, after comparing a pair of corresponding characters, it tries to increase the answer by $1$ whenever possible.

This algorithm is rather slow: it can compute the answer only in $O(n^2)$ time.

The naive algorithm is implemented as follows:

vector<int> d1(n), d2(n);
for (int i = 0; i < n; i++) {
  d1[i] = 1;
  while (0 <= i - d1[i] && i + d1[i] < n && s[i - d1[i]] == s[i + d1[i]]) {
    d1[i]++;
  }

  d2[i] = 0;
  while (0 <= i - d2[i] - 1 && i + d2[i] < n &&
         s[i - d2[i] - 1] == s[i + d2[i]]) {
    d2[i]++;
  }
}

d1 = [0] * n
d2 = [0] * n
for i in range(0, n):
    d1[i] = 1
    while 0 <= i - d1[i] and i + d1[i] < n and s[i - d1[i]] == s[i + d1[i]]:
        d1[i] += 1

    d2[i] = 0
    while 0 <= i - d2[i] - 1 and i + d2[i] < n and s[i - d2[i] - 1] == s[i + d2[i]]:
        d2[i] += 1

Manacher's algorithm

Here we describe only the case of finding all odd-length palindromic substrings, that is, computing only $d_1[]$; the algorithm for finding all even-length palindromic substrings (that is, computing $d_2[]$) requires only a few small modifications to the odd-length case.

To compute the values quickly, we maintain the boundaries $[l, r]$ of the rightmost palindromic substring found (that is, the palindrome with the maximum value of $r$, where $l$ and $r$ are the positions of its left and right boundaries, respectively). Initially, we set $l = 0$ and $r = -1$ (-1 should not be confused with a reverse-index position; it can be any negative number and is used only for convenience at the start of the loop).

Procedure

Suppose we are about to compute $d_1[i]$ for the next $i$, and all values in the preceding $d_1[]$ have already been computed. We compute it as follows:

• If $i$ lies outside the current palindromic substring, namely $i > r$, we invoke the naive algorithm.

  Thus, we increase $d_1[i]$ continuously, checking at each step whether the current substring $[i - d_1[i] \dots i + d_1[i]]$ ($d_1[i]$ denotes the radius here and below) is a palindrome. The algorithm stops when it finds the first pair of corresponding characters that differ, or when it reaches a boundary of $s$. In either case, we have computed $d_1[i]$. We must then remember to update $(l, r)$.

• Now consider the case $i \le r$. We will try to obtain information from the values of $d_1[]$ that have already been computed. First, reflect position $i$ within the palindromic substring $(l, r)$; this gives us $j = l + (r - i)$. Now consider the value $d_1[j]$. Since position $j$ is symmetric to position $i$, we can almost always set $d_1[i] = d_1[j]$. The idea is illustrated below (you can think of the palindrome centered at $j$ as being “copied” to the position centered at $i$):

  $$\ldots\ \overbrace{ s_l\ \ldots\ \underbrace{ s_{j-d_1[j]+1}\ \ldots\ s_j\ \ldots\ s_{j+d_1[j]-1} }_\text{palindrome}\ \ldots\ \underbrace{ s_{i-d_1[j]+1}\ \ldots\ s_i\ \ldots\ s_{i+d_1[j]-1} }_\text{palindrome}\ \ldots\ s_r }^\text{palindrome}\ \ldots$$

  However, there is a tricky case that must be handled correctly: when the “inner” palindrome reaches the boundary of the “outer” palindrome, that is, $j - d_1[j] + 1 \le l$ (or equivalently, $i + d_1[j] - 1 \ge r$). Since symmetry outside the range of the “outer” palindrome is not guaranteed, directly setting $d_1[i] = d_1[j]$ would be incorrect: we do not have enough information to assert that the palindrome at position $i$ has the same length.

  In fact, to handle this case correctly, we should “truncate” the length of the palindrome by setting $d_1[i] = r - i + 1$. We then run the naive algorithm to try to increase the value of $d_1[i]$ as much as possible.

  The case is illustrated below (the palindrome centered at $j$ has been truncated so that it lies within the “outer” palindrome):

  $$\ldots\ \overbrace{ \underbrace{ s_l\ \ldots\ s_j\ \ldots\ s_{j+(j-l)} }_\text{palindrome}\ \ldots\ \underbrace{ s_{i-(r-i)}\ \ldots\ s_i\ \ldots\ s_r }_\text{palindrome} }^\text{palindrome}\ \underbrace{ \ldots \ldots \ldots \ldots \ldots }_\text{try moving here}$$

  The illustration shows that although the palindrome centered at $j$ may be longer and extend beyond the “outer” palindrome, at position $i$ we can use only the part that lies entirely within the “outer” palindrome. However, the answer at position $i$ may be larger than this value, so we next run the naive algorithm to try to extend it beyond the “outer” palindrome, into the region marked “try moving here.”

Finally, it is worth emphasizing once more that we must remember to update $(l, r)$ after computing each $d_1[i]$.

Let us also repeat that the algorithm for computing the even-length palindrome array $d_2[]$ is very similar to the algorithm above for computing the odd-length palindrome array $d_1[]$.

Complexity of Manacher's algorithm

Since we always run the naive algorithm when computing the answer for a particular position, the fact that the algorithm has linear time complexity is not obvious at first glance.

However, a closer analysis shows that the algorithm is linear. Here we should point out that the algorithm for computing the Z-function is quite similar to this algorithm and also has linear time complexity.

In fact, observe that every iteration of the naive algorithm increases $r$ by $1$, and that $r$ never decreases during the execution of the algorithm. These two observations tell us that the naive algorithm performs $O(n)$ iterations in total.

The other part of Manacher's algorithm is clearly linear as well, so the total complexity is $O(n)$.

Implementation of Manacher's algorithm

Case analysis

To compute $d_1[]$, we use the following code:

C++

vector<int> d1(n);
for (int i = 0, l = 0, r = -1; i < n; i++) {
  int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
  while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
    k++;
  }
  d1[i] = k--;
  if (i + k > r) {
    l = i - k;
    r = i + k;
  }
}

Python

d1 = [0] * n
l, r = 0, -1
for i in range(0, n):
    k = 1 if i > r else min(d1[l + r - i], r - i + 1)
    while 0 <= i - k and i + k < n and s[i - k] == s[i + k]:
        k += 1
    d1[i] = k
    k -= 1
    if i + k > r:
        l = i - k
        r = i + k

The code for computing $d_2[]$ is very similar, but some arithmetic expressions are slightly different:

C++

vector<int> d2(n);
for (int i = 0, l = 0, r = -1; i < n; i++) {
  int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
  while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) {
    k++;
  }
  d2[i] = k--;
  if (i + k > r) {
    l = i - k - 1;
    r = i + k;
  }
}

Python

d2 = [0] * n
l, r = 0, -1
for i in range(0, n):
    k = 0 if i > r else min(d2[l + r - i + 1], r - i + 1)
    while 0 <= i - k - 1 and i + k < n and s[i - k - 1] == s[i + k]:
        k += 1
    d2[i] = k
    k -= 1
    if i + k > r:
        l = i - k - 1
        r = i + k

Unified treatment

Although we considered the computation of $d_1[]$ and $d_2[]$ separately in the explanation and implementations above, a trick can actually unify their computation as the computation of $d_1[]$.

Given a string $s$ of length $n$, we insert separators $\#$ into its $n + 1$ gaps, thereby constructing a string $s'$ of length $2n + 1$. For example, for $s = \mathtt{abababc}$, the corresponding string is $s' = \mathtt{\#a\#b\#a\#b\#a\#b\#c\#}$.

A $\#$ between two letters represents the corresponding “gap” in $s$. The $\#$ characters at the two ends are included for implementation convenience.

Notice that after computing $d_1[]$ for $s'$, for any position $i$, the longest palindromic substring described by $d_1[i]$ must end in a $\#$ (if it ended in a letter, then there would necessarily be a $\#$ on each side of that letter, so it could be extended outward by one to obtain a longer palindrome). Therefore, consider a maximal palindromic substring in $s$ centered at a letter, and let its length be $m + 1$. Its corresponding maximal palindromic substring in $s'$ is centered at the corresponding letter and has length $2m + 3$; meanwhile, consider a maximal palindromic substring in $s$ centered at a gap, and let its length be $m$. Its corresponding maximal palindromic substring in $s'$ is centered at the $\#$ representing that gap and has length $2m + 1$ (in both cases above, $m$ is even, but whether this property holds does not affect the conclusion). Combining these observations with a small amount of calculation, it is easy to see that in $s'$, $d_1[i]$ represents the total length plus one of the maximal palindromic substring centered at the corresponding position in $s$.

The conclusion above establishes the relationship between $d_1[]$ for $s'$ and $d_1[]$ and $d_2[]$ for $s$.

Since this unified treatment is essentially just computing $d_1[]$ for $s'$, after obtaining $s'$, the code is the same as the code for computing $d_1[]$ in the previous section.

Practice problems

• UVa #11475 "Extend to Palindrome"
• The Longest Double Palindromic Substring (National Training Team)
• CF1326D2. Labyrinth

This page is primarily translated from the blog post Нахождение всех подпалиндромов and its English translation, Finding all sub-palindromes in $O(N)$. The Russian version is licensed under Public Domain + Leave a Link; the English version is licensed under CC-BY-SA 4.0.