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}}\) (where \(t_{\text{rev}}\) is the reversed string of \(t\)).

Explanation

Obviously, there can be up to \(O(n^2)\) palindromic substrings in the worst case, so at first glance it seems there is no linear algorithm for this problem.

However, information about palindromes can be expressed in a more compact way: for each position \(i = 0 \dots n - 1\), we compute two values \(d_1[i]\) and \(d_2[i]\). They denote, respectively, the number of palindromes centered at position \(i\) with odd and even lengths. In other words, they represent the radius length of the longest odd-length and even-length palindrome centered at position \(i\) (the radius length \(d_1[i]\), \(d_2[i]\) is the number of characters from the center \(i\) to the rightmost character of the palindrome).

For example, the string \(s = \mathtt{abababc}\) has three odd-length palindromes centered at \(s[3] = b\), with the longest having radius \(3\), i.e., \(d_1[3] = 3\):

\[ a\ \overbrace{b\ a\ \underset{s_3}{b}\ a\ b}^{d_1[3]=3}\ c \]

The string \(s = \mathtt{cbaabd}\) has two even-length palindromes centered at \(s[3] = a\), with the longest having radius \(2\), i.e., \(d_2[3] = 2\):

\[ c\ \overbrace{b\ a\ \underset{s_3}{a}\ b}^{d_2[3]=2}\ d \]

Thus, the key idea is that if we have a palindrome of length \(l\) centered at position \(i\), then we also have palindromes of lengths \(l - 2\), \(l - 4\), etc., centered at \(i\). Therefore, the two arrays \(d_1[i]\) and \(d_2[i]\) are sufficient to represent all palindromic substrings in the string.

Surprisingly, there exists a linear-time algorithm that is simple enough to compute these two "palindromic arrays" \(d_1[]\) and \(d_2[]\). In this article, we will describe this algorithm in detail.

Solutions

In general, this problem can be solved in multiple ways: using string hashing, it can be solved in \(O(n \log n)\) time; using suffix arrays and fast LCA, it can be solved in \(O(n)\) time.

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

Naive Algorithm

To avoid ambiguity in the following discussion, we first clarify what the "naive algorithm" is.

This algorithm works as follows: for each center position \(i\), it tries to increment the answer by \(1\) as long as possible after comparing a pair of corresponding characters.

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

The implementation of the naive algorithm is as follows:

Implementation

C++Python

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 will only describe the algorithm for finding all odd-length palindromic substrings, i.e., computing \(d_1[]\); the algorithm for finding all even-length palindromic substrings (i.e., computing \(d_2[]\)) requires only minor modifications to the odd-length case.

For fast computation, we maintain the boundary \((l, r)\) of the rightmost palindromic substring found so far (i.e., the palindrome with the largest \(r\) value, where \(l\) and \(r\) are the positions of its left and right boundaries, respectively). Initially, we set \(l = 0\) and \(r = -1\) (the -1 here is distinct from reverse indexing; it can be any negative number, just for convenience in the initial loop).

Process

Now suppose we want to compute \(d_1[i]\) for the next \(i\), and all previous \(d_1[]\) values have already been computed. We compute it as follows:

• If \(i\) lies outside the current palindrome, i.e., \(i > r\), we invoke the naive algorithm.

  Thus, we continuously increase \(d_1[i]\), checking at each step whether the current substring \([i - d_1[i] \dots i + d_1[i]]\) (where \(d_1[i]\) denotes the radius length) is a palindrome. The algorithm stops when we find the first mismatch or reach the boundary of \(s\). In either case, we have computed \(d_1[i]\). Afterward, we must remember to update \((l, r)\).

• Now consider the case \(i \le r\). We try to extract some information from the already computed \(d_1[]\) values. First, mirror position \(i\) within the palindrome \((l, r)\), i.e., we get \(j = l + (r - i)\). Now consider the value \(d_1[j]\). Since position \(j\) is symmetric to position \(i\), we almost always can set \(d_1[i] = d_1[j]\). This idea is illustrated below (think of the palindrome centered at \(j\) 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, i.e., \(j - d_1[j] + 1 \le l\) (or equivalently, \(i + d_1[j] - 1 \ge r\)). Because symmetry is not guaranteed outside the "outer" palindrome, 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 palindrome length, i.e., set \(d_1[i] = r - i + 1\). After that, we run the naive algorithm to try to increase \(d_1[i]\) as much as possible.

  This situation is illustrated below (the palindrome centered at \(j\) has been truncated to lie 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 only use the part that lies entirely within the "outer" palindrome. However, the answer for position \(i\) might be larger than this value, so we then run the naive algorithm to try to extend it beyond the "outer" palindrome, i.e., into the region labeled "try moving here".

Finally, it is necessary to remember to update the values \((l, r)\) after computing each \(d_1[i]\).

Also, let us repeat: the algorithm for computing the even-length palindrome array \(d_2[]\) is very similar to the algorithm for computing the odd-length palindrome array \(d_1[]\) described above.

Complexity of Manacher's Algorithm

Since we always run the naive algorithm when computing the answer for a specific position, it is not immediately obvious that the algorithm runs in linear time.

However, a more careful analysis shows that the algorithm indeed has linear complexity. Here we note that the algorithm for computing the Z-function is similar and also has linear time complexity.

In fact, note that each iteration of the naive algorithm increases \(r\) by \(1\), and \(r\) never decreases during the algorithm's execution. These two observations tell us that the naive algorithm performs a total of \(O(n)\) iterations.

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

Implementation of Manacher's Algorithm

Separate Cases

To compute \(d_1[]\), we have the following code:

C++Python

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;
  }
}

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 with slight differences in the arithmetic expressions:

C++Python

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;
  }
}

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 Processing

Although we considered the computation of \(d_1[]\) and \(d_2[]\) separately in the explanation and the above implementations, they can actually be unified into a single computation of \(d_1[]\) using a trick.

Given a string \(s\) of length \(n\), we insert the separator \(\#\) into its \(n + 1\) gaps, constructing a string \(s'\) of length \(2n + 1\). For example, for \(s = \mathtt{abababc}\), we have \(s' = \mathtt{\#a\#b\#a\#b\#a\#b\#c\#}\).

The \(\#\) between letters corresponds to the "gaps" in \(s\). The \(\#\) at both ends are for implementation convenience.

Note that after computing \(d_1[]\) for \(s'\), for any position \(i\), the longest palindrome described by \(d_1[i]\) must end with \(\#\) (if it ended with a letter, since each letter is surrounded by \(\#\), we could extend it outward by one to get a longer palindrome). Therefore, for a maximal odd-length palindrome in \(s\) centered at a letter with length \(m + 1\), it corresponds to a maximal palindrome in \(s'\) centered at the corresponding letter with length \(2m + 3\); for a maximal even-length palindrome in \(s\) centered at a gap with length \(m\), it corresponds to a maximal palindrome in \(s'\) centered at the corresponding gap \(\#\) with length \(2m + 1\) (in both cases, \(m\) is even, but this property does not affect the conclusion). Combining these observations with a little calculation, it is easy to see that in \(s'\), \(d_1[i]\) represents the total length plus one of the maximal palindrome in \(s\) centered at the corresponding position.

The above conclusion establishes the relationship between \(d_1[]\) of \(s'\) and \(d_1[]\) and \(d_2[]\) of \(s\).

Since this unified processing essentially computes \(d_1[]\) for \(s'\), after obtaining \(s'\), the code is the same as that for computing \(d_1[]\) in the previous section.

Practice Problems

• UVa #11475 "Extend to Palindrome"
• 「National Training Team」Longest Double Palindrome
• CF1326D2. Labyrinth

This page is mainly 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.

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用