On this page

Palindromes & Manacher's Algorithm

Why this exists

A palindrome is a string that reads the same forwards and backwards: racecar, abba, a. Formally, is a palindrome when for every . A palindromic substring of is a contiguous piece that is a palindrome.

Three questions about palindromes come up again and again:

  1. What is the longest palindromic substring? (LeetCode 5, one of the most-asked string questions.)
  2. How many palindromic substrings are there, counting each position separately? (LeetCode 647.)
  3. How many distinct palindromes occur? (The palindromic tree answers this.)

The obvious answers are slow. Checking every substring is . Growing a palindrome outwards from every possible centre is , which is fine for and hopeless for . Manacher's algorithm answers questions 1 and 2 in time. Its trick will look familiar if you have read The Z-Algorithm: keep a window that you already understand (there, a copy of the prefix; here, a palindrome), and inside the window, look up answers instead of recomputing them. A palindrome is its own mirror image, so anything you learned on its left half is true on its right half.

The algorithm is due to Glenn Manacher (1975), who used it to find the shortest palindromic prefix of a string online, one character at a time. Apostolico, Breslauer and Galil (1995) observed that the same computation yields all maximal palindromes (the longest palindrome around every centre), which is how it is used today. Forty years later, Mikhail Rubinchik and Arseny Shur introduced the eertree (palindromic tree, 2015), a small automaton that stores every distinct palindrome of a string and is built in by adding one character at a time.

This lesson builds both from the ground up, with traces checked by a program, proofs, and code in four languages.

Pattern triggers

If the problem says or has…Think of…
"longest palindromic substring", up to Expand around each centre, , simplest to write
"longest palindromic substring", up to –Manacher,
"count palindromic substrings"Manacher:
"for every centre, how far does the palindrome reach"That is Manacher's radius arrays
"is a palindrome?" for many queries, static stringManacher (check the radius at the centre of ) or an table
"is a palindrome?" with character updatesForward and reverse hashes in a Fenwick tree (String Hashing)
"shortest palindrome by adding characters in front", "longest palindromic prefix"Manacher, or KMP / Z on s + '#' + reverse(s)
"number of distinct palindromic substrings", "occurrences of each palindrome"Palindromic tree (eertree)
"split into the fewest palindromes", "palindrome partitioning" DP (String DP); eertree with series links for
"longest palindromic subsequence" (letters may be skipped)Not this lesson: LCS with the reverse, or interval DP (Sequence DP)
"can the letters be rearranged into a palindrome"Not this lesson: count letters, at most one odd count (Hash Tables)

The meta-trigger: contiguous palindromes, many centres, and a size limit that rules out quadratic work.

Intuition & first principles

Centres

Every palindrome has a centre. An odd-length palindrome like aba is centred on a letter (the b). An even-length palindrome like abba is centred on the gap between two letters (between the two bs). A string of length has letter-centres and gap-centres, so centres in total.

Around one centre, palindromes are nested: if xabax is a palindrome centred on b, then so is aba, and so is b. Peel one letter off each end and you still have a palindrome with the same centre. So a single number describes every palindrome at a centre: its radius, the size of the largest one. Knowing the radius at every centre means knowing every palindromic substring.

We use two arrays, as in cp-algorithms:

  • = the number of odd palindromes centred at letter . The largest one is , of length . Always (the letter alone).
  • = the number of even palindromes centred on the gap between and . The largest one is , of length . It can be 0.

For abaaba:

012345
abaaba
121121
000300

says b and aba are centred at 1. says aa, baab and abaaba are centred on the gap before index 3. Add everything up: palindromic substrings. (Check: six single letters, aba twice, aa, baab, abaaba.)

The slow way, and the waste

The expand-around-centre method computes each radius independently: start at the centre and compare the letters on both sides, stepping outwards until they differ. On aaaaaaaa every centre expands all the way to an end of the string, and the total work is quadratic: 28 comparisons for 8 letters, 499,500 for 1,000 letters (a script counted both).

Here is what it wastes. Suppose we have found that = babcbab is a palindrome (centred at 4). Now we want the radius at 6. Position 6 is inside that big palindrome, and the big palindrome is a mirror: position 6 reflects to position . Everything around position 2, as long as we stay inside , is reflected around position 6. We already computed the radius at 2. So we can read most of the answer at 6 instead of recomputing it.

An everyday analogy: the folded paper

Write a word on a strip of paper, find a palindrome in it, and fold the strip at the palindrome's centre. The letters on the left half land exactly on the letters of the right half. A smaller palindrome on the left half lands on an identical smaller palindrome on the right half. As long as that smaller palindrome lies entirely on the folded part, you know its twin without reading the right half at all. Only if it reaches the edge of the fold do you have to look beyond the edge, at paper that was never folded.

That is the whole algorithm:

  • the fold is the box , the palindrome found so far that reaches furthest to the right;
  • the twin of position is its mirror ;
  • reading the twin is copying ;
  • the edge of the fold is , and we only compare letters beyond it.

If this sounds like the Z-box, it is the same idea. In Z, the box is a copy of the prefix and the mirror is ; here the box is a palindrome and the mirror is .

Mechanics

The box, drawn

Take = cbabcbabd. After processing centre 4 we know the box :

index:   0  1  2  3  4  5  6  7  8
s:       c  b  a  b  c  b  a  b  d
            [==================]          box [l, r] = [1, 7] = "babcbab", centred at 4
               ^           ^
               j = 2       i = 6           mirror j = l + r - i = 1 + 7 - 6 = 2

Reflection around the centre maps position to . It maps letters inside the box to equal letters inside the box (that is what "palindrome" means). So the palindrome centred at , as far as it stays inside the box, reflects to a palindrome centred at .

flowchart LR
    subgraph BOX["box s[l..r], a palindrome with centre c"]
        J["mirror j = l + r - i"]
        C["centre c"]
        I["current i"]
    end
    J -- "reflect around c" --> I
    J -. "d1[j] already known" .-> I
    BOX --> OUT["s[r+1..] unknown: compare only here"]

Three cases

Let : the number of letters from to the right edge of the box, included. Compare the mirror's radius with the room:

flowchart TD
    S["next centre i"] --> Q1{"i > r?"}
    Q1 -- "yes: right of every box" --> C0["start at k = 1 and expand"]
    Q1 -- "no" --> Q2{"compare d1[j] with room = r - i + 1"}
    Q2 -- "d1[j] < room" --> CA["Case A: inside the box, d1[i] = d1[j] exactly"]
    Q2 -- "d1[j] > room" --> CB["Case B: sticks out past l, d1[i] = room exactly"]
    Q2 -- "d1[j] = room" --> CC["Case C: touches the edge, d1[i] is at least room, expand past r"]
    C0 --> U["if the palindrome ends beyond r, move the box"]
    CC --> U
  • Case A: the mirror's palindrome lies strictly inside the box. Reflect it, mismatch and all, and you get the palindrome at . , no comparisons needed.
  • Case B: the mirror's palindrome sticks out past the left edge . Then the palindrome at stops exactly at the right edge: . (Proof below; the short version is that the letter just outside and the letter just outside differ, since otherwise the box would have been larger.)
  • Case C: the mirror's palindrome ends exactly at . We know the palindrome at reaches at least to , and nothing about beyond. Start at and compare letters past .

As in Z, one line handles all three: k = min(d1[j], r - i + 1), followed by the usual expansion loop. In cases A and B the loop's first comparison fails immediately (or the string ends); only case C and "outside the box" ever make a successful comparison.

The algorithm

MANACHER-ODD(s):
    n = length(s);  d1[0..n-1] = 0;  l = 0;  r = -1        # box [l, r]; r = -1 means "no box yet"
    for i = 0 .. n-1:
        k = 1 if i > r else min(d1[l + r - i], r - i + 1)  # copy from the mirror, cut at the box edge
        while i - k >= 0 and i + k < n and s[i - k] == s[i + k]:
            k += 1                                          # every success here reads s[i + k] beyond r
        d1[i] = k
        if i + k - 1 > r:                                   # reaches further right: move the box
            l, r = i - k + 1, i + k - 1

The even version is the same with three small changes, because the centre is the gap before : start from 0 instead of 1, compare with , and the mirror of the gap before is the gap before .

MANACHER-EVEN(s):
    d2[0..n-1] = 0;  l = 0;  r = -1
    for i = 0 .. n-1:
        k = 0 if i > r else min(d2[l + r - i + 1], r - i + 1)
        while i - k - 1 >= 0 and i + k < n and s[i - k - 1] == s[i + k]:
            k += 1
        d2[i] = k
        if i + k - 1 > r:
            l, r = i - k, i + k - 1

Trace table: odd radii on cbabcbabd

One row per centre. "Ok / fail" counts the successful and failing comparisons in the expansion loop. Every value below was produced by a script running the code in this lesson.

Box beforeMirror , , roomCaseStart Ok / failBox after
0cnone—outside10 / 01[0, 0]
1b[0, 0]—outside10 / 11[1, 1]
2a[1, 1]—outside12 / 03[0, 4]
3b[0, 4], 1, room 2A10 / 11[0, 4]
4c[0, 4], 1, room 1C13 / 14[1, 7]
5b[1, 7], 1, room 3A10 / 11[1, 7]
6a[1, 7], 3, room 2B20 / 12[1, 7]
7b[1, 7], 1, room 1C10 / 11[1, 7]
8d[1, 7]—outside10 / 01[1, 7]

Result: . The largest value is , so the longest odd palindrome is = babcbab, of length .

Walk through the interesting rows:

  • Row 2. Outside the box. Compare = b with = b (ok), then = c with = c (ok). Now : the string has run out on the left. , cbabc, and the box jumps to .
  • Row 4 (case C). Inside ; the mirror is with , and the room is . Equal, so we know only that c itself is a palindrome and must look beyond : b/b, a/a, b/b succeed, c/d fails. and the box becomes . All three successes read letters (5, 6, 7) that no earlier step had compared.
  • Row 6 (case B). The mirror has : its palindrome cbabc covers , which sticks out past . The room is only 2, so we start at and make one comparison: = c against = d, which fails, exactly as case B promises. Notice why it fails: is the letter just right of the box, and its reflection would be = c, which the box already proved differs from .
  • Rows 3 and 5 (case A). The mirror's palindrome is the single letter and lies inside the box. One comparison, which fails, as promised.

In total the loop made 5 successful and 6 failing comparisons, 11 in all. Plain expand-around-centre on the same string makes 12 for the odd centres (and 20 with the even centres, against Manacher's 19), so on a string this small Manacher barely helps. The gap opens on repetitive input: for copies of a, both arrays together cost 1,997 comparisons with Manacher against 499,500 without the mirror trick; at , 19,997 against 49,995,000.

In the player, the shaded window is the box , c marks its centre, mirror marks the position whose radius is reused, green pairs are successful comparisons and grey pairs mismatches. The radii table on the right fills in as . Watch the step for : the start value comes straight from the mirror, cut at the box edge.

The even pass on abaaba

The even array works the same way. On abaaba: at and , one comparison each fails (a/b, b/a). At , outside any box, compare / (a/a), / (b/b), / (a/a): all succeed and the string ends. and the box becomes , the whole string. At the mirror is the gap before , with , so starts at 0 and one comparison (a/b) fails. Same at . Result .

The other presentation: the # transform

Many textbooks (and the overview page of this module) avoid the second array by inserting a separator between letters: abaaba becomes #a#b#a#a#b#a#. Now every palindrome in the new string has odd length and a centre on a letter of : odd palindromes of are centred on letters, even palindromes of are centred on #s. One array suffices, where is the radius in not counting the centre:

#a#b#a#a#b#a#
0103016103010

A neat fact makes this work: is exactly the length of the corresponding palindrome in . The # at index 6 has , and abaaba has length 6. The conversions are and ; the implementation below was cross-checked against these on 3,000 random strings. Some versions also add distinct sentinels at both ends (^#a#b#…#$) so the expansion loop needs no bounds checks.

Which to use? The # version is one loop instead of two and the most common in interview answers. The / version uses half the memory, avoids building a new string, and gives the two arrays you actually want for counting and for prefix questions. They are the same algorithm; pick one and learn its index arithmetic cold.

The ladder: brute force → better → optimal

Problem: find the longest palindromic substring of (and, with the same machinery, count all palindromic substrings).

Rung 1: check every substring,

There are substrings; checking one costs up to its length. For that is 500,500 substrings and on the order of letter comparisons. Its only use is as a test oracle: every implementation in this lesson was checked against it on thousands of random strings.

Rung 2: expand around every centre, time, space

Try each of the centres and expand while the two sides agree. The work at a centre is its radius plus one failed comparison, so the total is . On random text over a big alphabet the radii are tiny and this is effectively linear; on aaaa…a it is quadratic. It is short, uses no memory, and is the answer most interviewers expect first.

def longest_palindrome_expand(s):
    best = (0, 0)                                  # (length, start)
    for centre in range(2 * len(s) - 1):
        lo, hi = centre // 2, (centre + 1) // 2    # same index: odd; neighbours: even
        while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
            lo, hi = lo - 1, hi + 1
        best = max(best, (hi - lo - 1, lo + 1))
    return s[best[1]:best[1] + best[0]]

Rung 3: dynamic programming over intervals, time and space

Let be true when is a palindrome. Then : a range is a palindrome when its ends match and its inside is a palindrome. Fill by increasing length. This is the interval-DP shape from Interval DP, and it is not faster than rung 2. Its value is the table: after work you can answer "is a palindrome?" in , which is exactly what palindrome partitioning needs. The table is also the bridge to the subsequence version, where letters may be skipped, covered in Sequence DP.

Hash and its reverse once (String Hashing). Then "is a palindrome?" is one comparison: the forward hash of against the hash of the matching range of the reversed string. At each centre, palindromes are nested, so "the radius is at least " is monotone in , and binary search finds each radius with hash checks. Total , randomised (a hash collision can make it wrong with tiny probability). It is a useful fallback when you also need palindrome checks on changing strings, which Manacher cannot handle.

Rung 5: Manacher,

Reuse the mirror inside the box and compare only beyond . Deterministic, linear, memory for the radius arrays.

RungMethodTimeExtra spaceWhy it is better than the rung above
1All substringsBaseline and test oracle
2Expand around centres worst, near-linear on random textNested palindromes: one expansion per centre covers all its palindromes
3Interval DP tableSame time, but answers any "is a palindrome" in afterwards
4Hashing + binary searchEach radius in ; works with updates (Fenwick)
5ManacherMirror reuse; the box edge only moves right

Correctness

We need: the start value is never more than the true radius, and in cases A and B it is exactly the true radius. The loop then finishes the job, because it stops at the first mismatch or at the end of the string, which is the definition of the radius.

Invariant. When the box is with , is a palindrome with centre , and it is maximal: either , or , or . It is set right after the expansion loop stopped, so both hold.

Fix with (inside the box; note , because the box was set by a centre that reached ), its mirror , and . Reflection maps the box to itself and preserves letters: for .

Claim 1 (lower bound). . Let . The palindrome exists (because ) and lies inside the box (because keeps its left end , and its right end is since ). Reflecting it letter by letter gives , which is therefore a palindrome too.

Claim 2 (case A is exact). If , the palindrome at stopped because , and both positions are inside the box ( by the case condition). Their reflections are and , so and the palindrome at stops at the same radius. (The case condition gives and , so the mirror's palindrome really stopped at a mismatch inside the box, not at an end of the string.)

Claim 3 (case B is exact). If , the palindrome at covers (so ), and its reflection around is , which lies inside the box. So . Reflecting around the box centre gives . So . On the other side, . By maximality of the box, (or ). Therefore , and the radius at is exactly the room.

Case C needs nothing: Claim 1 gives the lower bound and the loop extends it.

Even centres. The same three claims hold with the even box; the mirror of the gap before is the gap before and all index shifts follow from the definition of . The implementation below compares both arrays against the brute-force definition on 3,000 random strings over alphabets of size 1–3 in every language.

Complexity

Time: , by watching . Split the loop's comparisons into failures and successes.

  • Failures. Each centre ends with at most one failed comparison. At most per array.
  • Successes. A successful comparison at centre reads . Where is that relative to ? If (outside), . In case C, starts at , so the first letter read is . In cases A and B, Claims 2 and 3 say the first comparison fails, so there are no successes. So every success reads a letter to the right of the current box, and right after the loop the box moves to cover it. The right edge only ever moves right and never passes , so there are at most successes per array.

So each array costs at most comparisons plus bookkeeping per centre: in total. On cbabcbabd the odd pass used 11 comparisons, under the bound of 18. On copies of a, both passes together used 19,997.

This is the third time in this module that "a right edge that only moves forward pays for all the work" proves linearity: the same potential argument powers the Z-algorithm (the Z-box), KMP (the current match length) and the two-pointer and sliding-window patterns.

Space. for the radius arrays (or for the transformed string and its array in the # version, about twice as much).

Best, average, worst. All , since every centre is visited. Random text over a large alphabet costs about one failed comparison per centre; highly repetitive text costs about two comparisons per centre.

Online. The odd pass computes only after it has looked as far right as the palindrome at reaches, so the radii are not online. But the set of palindromes that end at position is determined once the prefix is known, and Manacher's original paper was about exactly that online question (the shortest palindromic prefix). For "palindromes ending here" in an online setting, the eertree below is the cleaner tool.

Implementation

The radius arrays, the longest palindromic substring, the number of palindromic substrings, and the longest palindromic prefix (which gives the shortest palindrome, LeetCode 214). Each language asserts the traces above and then compares everything against brute force on 3,000 random strings.

import random


def manacher(s):
    """d1[i]: number of odd palindromes centred at i (the longest has length 2*d1[i] - 1).
    d2[i]: number of even palindromes centred between i-1 and i (the longest has length 2*d2[i])."""
    n = len(s)
    d1, d2 = [0] * n, [0] * n
    l, r = 0, -1                      # box: the odd palindrome s[l..r] reaching furthest right
    for i in range(n):
        k = 1 if i > r else min(d1[l + r - i], r - i + 1)
        while i - k >= 0 and i + k < n and s[i - k] == s[i + k]:
            k += 1
        d1[i] = k
        if i + k - 1 > r:
            l, r = i - k + 1, i + k - 1
    l, r = 0, -1                      # box: the even palindrome s[l..r] reaching furthest right
    for i in range(n):
        k = 0 if i > r else min(d2[l + r - i + 1], r - i + 1)
        while i - k - 1 >= 0 and i + k < n and s[i - k - 1] == s[i + k]:
            k += 1
        d2[i] = k
        if i + k - 1 > r:
            l, r = i - k, i + k - 1
    return d1, d2


def longest_palindrome(s):
    d1, d2 = manacher(s)
    best_len, best_start = 0, 0
    for i in range(len(s)):
        if 2 * d1[i] - 1 > best_len:
            best_len, best_start = 2 * d1[i] - 1, i - d1[i] + 1
        if 2 * d2[i] > best_len:
            best_len, best_start = 2 * d2[i], i - d2[i]
    return s[best_start:best_start + best_len]


def count_palindromes(s):
    d1, d2 = manacher(s)
    return sum(d1) + sum(d2)          # every centre contributes one palindrome per unit of radius


def longest_palindromic_prefix(s):
    d1, d2 = manacher(s)
    best = 0
    for i in range(len(s)):
        if d1[i] == i + 1:            # odd palindrome centred at i reaches index 0
            best = max(best, 2 * i + 1)
        if d2[i] == i:                # even palindrome centred before i reaches index 0
            best = max(best, 2 * i)
    return best


def shortest_palindrome(s):
    """Fewest characters added in front (LeetCode 214): mirror everything after the palindromic prefix."""
    k = longest_palindromic_prefix(s)
    return s[k:][::-1] + s


def is_pal(t):
    return t == t[::-1]


if __name__ == "__main__":
    assert manacher("cbabcbabd") == ([1, 1, 3, 1, 4, 1, 2, 1, 1], [0] * 9)
    assert manacher("abaaba") == ([1, 2, 1, 1, 2, 1], [0, 0, 0, 3, 0, 0])
    assert longest_palindrome("cbabcbabd") == "babcbab"
    assert longest_palindrome("cbbd") == "bb" and longest_palindrome("") == ""
    assert count_palindromes("abaaba") == 11 and count_palindromes("aaa") == 6
    assert shortest_palindrome("aacecaaa") == "aaacecaaa"
    assert shortest_palindrome("abcd") == "dcbabcd"
    rng = random.Random(1)
    for _ in range(3000):
        s = "".join(rng.choice("abc"[:rng.randint(1, 3)]) for _ in range(rng.randint(0, 14)))
        n = len(s)
        pals = [(i, j) for i in range(n) for j in range(i + 1, n + 1) if is_pal(s[i:j])]
        d1, d2 = manacher(s)
        for i in range(n):
            assert d1[i] == max(k for k in range(1, n + 1) if i - k + 1 >= 0 and i + k <= n and is_pal(s[i - k + 1:i + k]))
            assert d2[i] == max([0] + [k for k in range(1, n + 1) if i - k >= 0 and i + k <= n and is_pal(s[i - k:i + k])])
        assert len(longest_palindrome(s)) == max([0] + [j - i for i, j in pals])
        assert is_pal(longest_palindrome(s)) and longest_palindrome(s) in s
        assert count_palindromes(s) == len(pals)
        assert longest_palindromic_prefix(s) == max([0] + [j for i, j in pals if i == 0])
    print("ok")
import java.util.Random;

public class Manacher {
    /** Returns {d1, d2}: the longest odd palindrome at i has length 2*d1[i]-1, the longest even one 2*d2[i]. */
    static int[][] manacher(String s) {
        int n = s.length();
        int[] d1 = new int[n], d2 = new int[n];
        for (int i = 0, l = 0, r = -1; i < n; i++) {
            int k = i > r ? 1 : Math.min(d1[l + r - i], r - i + 1);
            while (i - k >= 0 && i + k < n && s.charAt(i - k) == s.charAt(i + k)) k++;
            d1[i] = k;
            if (i + k - 1 > r) { l = i - k + 1; r = i + k - 1; }
        }
        for (int i = 0, l = 0, r = -1; i < n; i++) {
            int k = i > r ? 0 : Math.min(d2[l + r - i + 1], r - i + 1);
            while (i - k - 1 >= 0 && i + k < n && s.charAt(i - k - 1) == s.charAt(i + k)) k++;
            d2[i] = k;
            if (i + k - 1 > r) { l = i - k; r = i + k - 1; }
        }
        return new int[][]{d1, d2};
    }

    static String longestPalindrome(String s) {
        int[][] d = manacher(s);
        int bestLen = 0, bestStart = 0;
        for (int i = 0; i < s.length(); i++) {
            if (2 * d[0][i] - 1 > bestLen) { bestLen = 2 * d[0][i] - 1; bestStart = i - d[0][i] + 1; }
            if (2 * d[1][i] > bestLen) { bestLen = 2 * d[1][i]; bestStart = i - d[1][i]; }
        }
        return s.substring(bestStart, bestStart + bestLen);
    }

    static long countPalindromes(String s) {
        int[][] d = manacher(s);
        long total = 0;
        for (int i = 0; i < s.length(); i++) total += d[0][i] + d[1][i];
        return total;
    }

    static int longestPalindromicPrefix(String s) {
        int[][] d = manacher(s);
        int best = 0;
        for (int i = 0; i < s.length(); i++) {
            if (d[0][i] == i + 1) best = Math.max(best, 2 * i + 1);
            if (d[1][i] == i) best = Math.max(best, 2 * i);
        }
        return best;
    }

    static String shortestPalindrome(String s) {
        int k = longestPalindromicPrefix(s);
        return new StringBuilder(s.substring(k)).reverse() + s;
    }

    static boolean isPal(String s, int a, int b) {             // s[a..b), b exclusive
        for (b--; a < b; a++, b--) if (s.charAt(a) != s.charAt(b)) return false;
        return true;
    }

    static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }

    public static void main(String[] args) {
        int[][] d = manacher("cbabcbabd");
        check(java.util.Arrays.equals(d[0], new int[]{1, 1, 3, 1, 4, 1, 2, 1, 1}), "d1");
        check(java.util.Arrays.equals(manacher("abaaba")[1], new int[]{0, 0, 0, 3, 0, 0}), "d2");
        check(longestPalindrome("cbabcbabd").equals("babcbab"), "longest");
        check(longestPalindrome("cbbd").equals("bb"), "cbbd");
        check(countPalindromes("abaaba") == 11 && countPalindromes("aaa") == 6, "count");
        check(shortestPalindrome("aacecaaa").equals("aaacecaaa"), "lc214 a");
        check(shortestPalindrome("abcd").equals("dcbabcd"), "lc214 b");
        Random rng = new Random(1);
        for (int it = 0; it < 3000; it++) {
            int sigma = 1 + rng.nextInt(3), n = rng.nextInt(15);
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) sb.append((char) ('a' + rng.nextInt(sigma)));
            String s = sb.toString();
            long count = 0;
            int longest = 0, prefix = 0;
            for (int i = 0; i < n; i++)
                for (int j = i + 1; j <= n; j++)
                    if (isPal(s, i, j)) { count++; longest = Math.max(longest, j - i); if (i == 0) prefix = j; }
            check(countPalindromes(s) == count, "count " + s);
            String lp = longestPalindrome(s);
            check(lp.length() == longest && isPal(lp, 0, lp.length()) && s.contains(lp), "longest " + s);
            check(longestPalindromicPrefix(s) == prefix, "prefix " + s);
        }
        System.out.println("ok");
    }
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <string>
#include <utility>
#include <vector>

// d1[i]: odd palindromes centred at i (longest 2*d1[i]-1); d2[i]: even ones centred before i (longest 2*d2[i]).
std::pair<std::vector<int>, std::vector<int>> manacher(const std::string& s) {
    int n = static_cast<int>(s.size());
    std::vector<int> d1(n), d2(n);
    for (int i = 0, l = 0, r = -1; i < n; ++i) {
        int k = i > r ? 1 : std::min(d1[l + r - i], r - i + 1);
        while (i - k >= 0 && i + k < n && s[i - k] == s[i + k]) ++k;
        d1[i] = k;
        if (i + k - 1 > r) { l = i - k + 1; r = i + k - 1; }
    }
    for (int i = 0, l = 0, r = -1; i < n; ++i) {
        int k = i > r ? 0 : std::min(d2[l + r - i + 1], r - i + 1);
        while (i - k - 1 >= 0 && i + k < n && s[i - k - 1] == s[i + k]) ++k;
        d2[i] = k;
        if (i + k - 1 > r) { l = i - k; r = i + k - 1; }
    }
    return {d1, d2};
}

std::string longestPalindrome(const std::string& s) {
    auto [d1, d2] = manacher(s);
    int bestLen = 0, bestStart = 0;
    for (int i = 0; i < static_cast<int>(s.size()); ++i) {
        if (2 * d1[i] - 1 > bestLen) { bestLen = 2 * d1[i] - 1; bestStart = i - d1[i] + 1; }
        if (2 * d2[i] > bestLen) { bestLen = 2 * d2[i]; bestStart = i - d2[i]; }
    }
    return s.substr(bestStart, bestLen);
}

long long countPalindromes(const std::string& s) {
    auto [d1, d2] = manacher(s);
    long long total = 0;
    for (std::size_t i = 0; i < s.size(); ++i) total += d1[i] + d2[i];
    return total;
}

int longestPalindromicPrefix(const std::string& s) {
    auto [d1, d2] = manacher(s);
    int best = 0;
    for (int i = 0; i < static_cast<int>(s.size()); ++i) {
        if (d1[i] == i + 1) best = std::max(best, 2 * i + 1);
        if (d2[i] == i) best = std::max(best, 2 * i);
    }
    return best;
}

std::string shortestPalindrome(const std::string& s) {
    std::string rest = s.substr(longestPalindromicPrefix(s));
    std::reverse(rest.begin(), rest.end());
    return rest + s;
}

bool isPal(const std::string& t) { return std::equal(t.begin(), t.end(), t.rbegin()); }

int main() {
    assert((manacher("cbabcbabd").first == std::vector<int>{1, 1, 3, 1, 4, 1, 2, 1, 1}));
    assert((manacher("abaaba").second == std::vector<int>{0, 0, 0, 3, 0, 0}));
    assert(longestPalindrome("cbabcbabd") == "babcbab" && longestPalindrome("cbbd") == "bb");
    assert(countPalindromes("abaaba") == 11 && countPalindromes("aaa") == 6);
    assert(shortestPalindrome("aacecaaa") == "aaacecaaa" && shortestPalindrome("abcd") == "dcbabcd");
    std::mt19937 rng(1);
    for (int it = 0; it < 3000; ++it) {
        int sigma = 1 + rng() % 3, n = rng() % 15;
        std::string s;
        for (int i = 0; i < n; ++i) s += static_cast<char>('a' + rng() % sigma);
        long long count = 0;
        int longest = 0, prefix = 0;
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j <= n; ++j)
                if (isPal(s.substr(i, j - i))) { ++count; longest = std::max(longest, j - i); if (i == 0) prefix = j; }
        assert(countPalindromes(s) == count);
        std::string lp = longestPalindrome(s);
        assert(static_cast<int>(lp.size()) == longest && isPal(lp) && s.find(lp) != std::string::npos);
        assert(longestPalindromicPrefix(s) == prefix);
    }
    std::cout << "ok\n";
    return 0;
}
/** d1[i]: odd palindromes centred at i (longest 2*d1[i]-1); d2[i]: even ones centred before i (longest 2*d2[i]). */
export function manacher(s: string): [number[], number[]] {
  const n = s.length;
  const d1: number[] = new Array(n).fill(0);
  const d2: number[] = new Array(n).fill(0);
  for (let i = 0, l = 0, r = -1; i < n; i++) {
    let k = i > r ? 1 : Math.min(d1[l + r - i], r - i + 1);
    while (i - k >= 0 && i + k < n && s[i - k] === s[i + k]) k++;
    d1[i] = k;
    if (i + k - 1 > r) {
      l = i - k + 1;
      r = i + k - 1;
    }
  }
  for (let i = 0, l = 0, r = -1; i < n; i++) {
    let k = i > r ? 0 : Math.min(d2[l + r - i + 1], r - i + 1);
    while (i - k - 1 >= 0 && i + k < n && s[i - k - 1] === s[i + k]) k++;
    d2[i] = k;
    if (i + k - 1 > r) {
      l = i - k;
      r = i + k - 1;
    }
  }
  return [d1, d2];
}

export function longestPalindrome(s: string): string {
  const [d1, d2] = manacher(s);
  let bestLen = 0;
  let bestStart = 0;
  for (let i = 0; i < s.length; i++) {
    if (2 * d1[i] - 1 > bestLen) [bestLen, bestStart] = [2 * d1[i] - 1, i - d1[i] + 1];
    if (2 * d2[i] > bestLen) [bestLen, bestStart] = [2 * d2[i], i - d2[i]];
  }
  return s.slice(bestStart, bestStart + bestLen);
}

export function countPalindromes(s: string): number {
  const [d1, d2] = manacher(s);
  return d1.reduce((a, b) => a + b, 0) + d2.reduce((a, b) => a + b, 0);
}

export function longestPalindromicPrefix(s: string): number {
  const [d1, d2] = manacher(s);
  let best = 0;
  for (let i = 0; i < s.length; i++) {
    if (d1[i] === i + 1) best = Math.max(best, 2 * i + 1);
    if (d2[i] === i) best = Math.max(best, 2 * i);
  }
  return best;
}

export function shortestPalindrome(s: string): string {
  const k = longestPalindromicPrefix(s);
  return [...s.slice(k)].reverse().join("") + s;
}

const isPal = (t: string): boolean => t === [...t].reverse().join("");
const same = (a: number[], b: number[]): boolean => a.length === b.length && a.every((x, i) => x === b[i]);

if (!same(manacher("cbabcbabd")[0], [1, 1, 3, 1, 4, 1, 2, 1, 1])) throw new Error("d1");
if (!same(manacher("abaaba")[1], [0, 0, 0, 3, 0, 0])) throw new Error("d2");
if (longestPalindrome("cbabcbabd") !== "babcbab" || longestPalindrome("cbbd") !== "bb") throw new Error("longest");
if (countPalindromes("abaaba") !== 11 || countPalindromes("aaa") !== 6) throw new Error("count");
if (shortestPalindrome("aacecaaa") !== "aaacecaaa" || shortestPalindrome("abcd") !== "dcbabcd") throw new Error("lc214");
for (let it = 0; it < 3000; it++) {
  const sigma = 1 + Math.floor(Math.random() * 3);
  const n = Math.floor(Math.random() * 15);
  let s = "";
  for (let i = 0; i < n; i++) s += "abc"[Math.floor(Math.random() * sigma)];
  let count = 0;
  let longest = 0;
  let prefix = 0;
  for (let i = 0; i < n; i++)
    for (let j = i + 1; j <= n; j++)
      if (isPal(s.slice(i, j))) {
        count++;
        longest = Math.max(longest, j - i);
        if (i === 0) prefix = j;
      }
  const lp = longestPalindrome(s);
  if (countPalindromes(s) !== count) throw new Error("count " + s);
  if (lp.length !== longest || !isPal(lp) || !s.includes(lp)) throw new Error("longest " + s);
  if (longestPalindromicPrefix(s) !== prefix) throw new Error("prefix " + s);
}
console.log("ok");

Language notes. In Java and C++ the count of palindromic substrings can reach , about for , so it is a long / long long. JavaScript strings index by UTF-16 code unit: a palindrome check on text containing emoji will compare half-characters; convert with Array.from(s) first if the input is user text (see Strings in Depth). The pure-Python version handles around characters in a couple of seconds, which is enough for most judges.

Palindromic prefixes and the shortest palindrome

A palindromic prefix is a prefix that is a palindrome. The longest one answers LeetCode 214: to make a palindrome by adding letters only in front, keep the longest palindromic prefix as the middle and mirror the rest. For aacecaaa, the longest palindromic prefix is aacecaa (length 7), the leftover is a, and the answer is a + aacecaaa = aaacecaaa.

There are three linear-time ways to find it, and it is worth knowing all three, because they show how the module's tools connect.

  1. Manacher. A palindrome reaches index 0 exactly when its radius equals the distance to the start: (odd, length ) or (even, length ). Take the largest. This is longest_palindromic_prefix above.
  2. KMP. is a palindrome exactly when it equals the last letters of . So it is a border (a prefix that is also a suffix) of , and the separator # keeps borders from crossing the middle. The last value of the prefix function of that string is the answer.
  3. Z. Same string, read by starting positions: the largest in the reversed half with equal to the total length (Z-algorithm, Applications).
def longest_pal_prefix_kmp(s):
    t = s + "#" + s[::-1]                 # '#' must not occur in s
    pi = [0] * len(t)
    for i in range(1, len(t)):
        k = pi[i - 1]
        while k > 0 and t[i] != t[k]:
            k = pi[k - 1]
        pi[i] = k + (t[i] == t[k])
    return pi[-1] if s else 0

assert longest_pal_prefix_kmp("aacecaaa") == 7 and longest_pal_prefix_kmp("abcd") == 1

Manacher's original 1975 paper solved a cousin of this problem: find the shortest palindromic prefix (of length at least 2) online, reading one letter at a time. That is why the paper's title says "on-line".

The hashing alternative

String hashing gives an algorithm that many people find easier to get right under pressure, and that extends to problems Manacher cannot touch.

Compute prefix hashes of and of . The substring corresponds to in the reverse, and is a palindrome exactly when the two have equal hashes (up to a collision, probability about per check for modulus ). Then:

  • All radii. At each centre, binary search the largest radius whose window is a palindrome: hash checks per centre, in total.
  • Longest palindrome by length. Among odd lengths, "some palindrome of length exists" is monotone (remove both ends of a palindrome of length to get one of length ), so binary search over odd values and, separately, over even values; each test slides a window of length in . Total .
  • With updates. Store the hash terms in a Fenwick tree for the forward and the reversed string; a letter change is two point updates and "is a palindrome?" is two range queries. That is CSES 2420 Palindrome Queries, where Manacher would have to be rerun after every change.

Hashing is Monte Carlo: it can be wrong with small probability, and adversarial tests can break a fixed modulus (see the anti-hash discussion on the hashing page). Manacher is deterministic and faster; prefer it when the string is static.

The palindromic tree (eertree)

Manacher gives the longest palindrome at every centre. It does not directly tell you how many different palindromes occur: in aaaa the substring aa occurs three times, and counting distinct strings requires knowing which occurrences are the same string. The eertree (Rubinchik and Shur; the name is "tree" with an extra "ee", itself a palindrome joke) stores every distinct palindrome of a string exactly once, as a node.

A surprising bound: at most distinct palindromes

Claim. A string of length has at most distinct non-empty palindromic substrings (at most if you count the empty string).

Proof idea. Build the string one letter at a time. When you append a letter , every new palindrome must end at the new letter, so it is a palindromic suffix of the new string. Let be the longest palindromic suffix, and any shorter one. is a suffix of ; since is a palindrome, reading backwards shows that is also a prefix of . That prefix occurrence ends before the last letter, so already occurred before was appended. Only can be new. So each letter adds at most one new distinct palindrome: at most in total.

The bound is tight: aaaa has exactly 4 (a, aa, aaa, aaaa), and so does abcd. It also tells us something about the algorithm: when adding a letter, the only candidate for a new node is the longest palindromic suffix, so there is at most one new node per letter.

The structure

  • Nodes are distinct palindromes, each stored by its length (the letters can be recovered from any occurrence).
  • Two roots. Root is an imaginary palindrome of length ; root is the empty palindrome. They exist so that "wrap a letter around a palindrome" always has something to wrap: wrapping around the empty string gives cc (length ); wrapping around the imaginary root gives c (length ).
  • Edges. An edge labelled from node goes to the palindrome . Every non-root node has exactly one incoming edge, so the edges form two trees, one for odd lengths (under root ) and one for even lengths (under root ).
  • Suffix links. The suffix link of points to the longest proper palindromic suffix of . Single letters link to root 0; root 0 links to root ; root links to itself. Following links from any node walks through all palindromic suffixes of that palindrome, longest first.
  • last points to the longest palindromic suffix of the string read so far.

Adding a letter

To append at position :

  1. Find the wrapper. Starting at last, follow suffix links until you reach a node such that the letter just before 's occurrence equals : . Then is the longest palindromic suffix of the new string. Root always qualifies, because and .
  2. If already has an edge , the palindrome is old: set last to it. Done.
  3. Otherwise create the node with length . Its suffix link: if its length is 1, link to root 0. Else keep following suffix links from until a node with ; the link is 's child , which must already exist (it is a shorter palindromic suffix, so by the bound proof it occurred before).

Trace: building the eertree of eertree

letterlinks followed in step 1wrapper longest palindromic suffixnew node?its suffix linkdistinct so far
0e1root eyesroot 01
1e1root 0eeyese2
2r3root ryesroot 03
3t2root tyesroot 04
4r0trtryesr5
5e0rtrertreyese6
6e0ertreeertreeyesee7

Seven letters, seven distinct palindromes: the bound is met with equality. Counting every occurrence instead (the number of palindromic substrings by position, as Manacher counts them) gives 12, because e occurs four times and r twice; the code below recovers that 12 from the eertree as well.

At step 1 walks three links: from ee, whose preceding letter would be off the string, to e (preceded by e, not r), to root 0 (preceded by e), to root , which always works. At , the suffix link of the new node eertree is found by walking from : e is preceded by r (fail), root 0 is preceded by e (success), so the link is root 0's child ee.

flowchart TD
    RM["root -1 (imaginary)"]
    R0["root 0 (empty)"]
    E["e"]
    EE["ee"]
    R["r"]
    T["t"]
    RTR["rtr"]
    ERTRE["ertre"]
    EERTREE["eertree"]
    RM -- "e" --> E
    RM -- "r" --> R
    RM -- "t" --> T
    R0 -- "e" --> EE
    T -- "r" --> RTR
    RTR -- "e" --> ERTRE
    ERTRE -- "e" --> EERTREE
    R0 -.-> RM
    E -.-> R0
    R -.-> R0
    T -.-> R0
    EE -.-> E
    RTR -.-> R
    ERTRE -.-> E
    EERTREE -.-> EE

Solid arrows are edges (wrap a letter around), dashed arrows are suffix links.

Why it is amortised

The two link-following loops are the only non-constant work. Each is paid for by a quantity that only moves one step left per letter.

  • Step 1. Let be the start position of the longest palindromic suffix (last). Each link followed moves to a shorter palindromic suffix, so its start position grows by at least 1. The new last is , which starts one position before . So if step 1 follows links, . Rearranged, ; summed over all letters this telescopes to at most links.
  • Step 3. The same argument applied to the start of the second-longest palindromic suffix (the suffix link of last) shows that this walk also follows links in total. Rubinchik and Shur give the full proof.

With transitions stored in arrays of size (the alphabet size), each step is and memory is ; with hash maps or balanced trees, memory is and each transition costs expected or .

What the eertree answers

  • Number of distinct palindromes: number of nodes minus the two roots.
  • Occurrences of each palindrome: count how many times each node was last, then push counts along suffix links from the longest nodes to the shortest (every occurrence of as a longest suffix is also an occurrence of all its palindromic suffixes). The sum over all nodes is the number of palindromic substrings, the same number Manacher gives.
  • Palindromes ending at each position: the depth of last in the suffix-link tree.
  • Online. It works one letter at a time, so it handles streams and "after each prefix, how many distinct palindromes?" queries.
import random


class Eertree:
    """Palindromic tree. Node 0: imaginary root (length -1). Node 1: empty root (length 0)."""

    def __init__(self):
        self.length = [-1, 0]
        self.link = [0, 0]             # root -1 links to itself, root 0 links to root -1
        self.next = [{}, {}]           # next[v][c] = node for c + palindrome(v) + c
        self.count = [0, 0]            # times the node was the longest palindromic suffix
        self.s = []
        self.last = 1

    def _climb(self, v, i):
        """Follow suffix links from v until the letter before v's occurrence equals s[i]."""
        while True:
            L = self.length[v]
            if i - L - 1 >= 0 and self.s[i - L - 1] == self.s[i]:
                return v
            v = self.link[v]

    def add(self, c):
        self.s.append(c)
        i = len(self.s) - 1
        v = self._climb(self.last, i)
        if c not in self.next[v]:
            w = len(self.length)
            self.length.append(self.length[v] + 2)
            self.next.append({})
            self.count.append(0)
            self.link.append(1 if self.length[w] == 1 else self.next[self._climb(self.link[v], i)][c])
            self.next[v][c] = w
        self.last = self.next[v][c]
        self.count[self.last] += 1

    def distinct(self):
        return len(self.length) - 2

    def total_occurrences(self):
        cnt = self.count[:]
        for v in range(len(cnt) - 1, 1, -1):    # children were created after their suffix links
            cnt[self.link[v]] += cnt[v]
        return sum(cnt[2:])


def build(s):
    t = Eertree()
    for c in s:
        t.add(c)
    return t


if __name__ == "__main__":
    t = build("eertree")
    assert t.distinct() == 7 and t.total_occurrences() == 12
    assert build("abacaba").distinct() == 7 and build("aaaa").distinct() == 4
    assert build("aaaa").total_occurrences() == 10 and build("").distinct() == 0
    rng = random.Random(1)
    for _ in range(3000):
        s = "".join(rng.choice("abc"[:rng.randint(1, 3)]) for _ in range(rng.randint(0, 16)))
        pals = [s[i:j] for i in range(len(s)) for j in range(i + 1, len(s) + 1) if s[i:j] == s[i:j][::-1]]
        t = build(s)
        assert t.distinct() == len(set(pals)) <= len(s)
        assert t.total_occurrences() == len(pals)
    print("ok")
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;

public class Eertree {
    // Node 0: imaginary root (length -1). Node 1: empty root (length 0). Lowercase letters only.
    private final List<Integer> len = new ArrayList<>(), link = new ArrayList<>(), count = new ArrayList<>();
    private final List<int[]> next = new ArrayList<>();
    private final StringBuilder s = new StringBuilder();
    private int last = 1;

    Eertree() {
        newNode(-1, 0);
        newNode(0, 0);
    }

    private int newNode(int length, int suffixLink) {
        len.add(length); link.add(suffixLink); count.add(0); next.add(new int[26]);   // 0 = no edge
        return len.size() - 1;
    }

    private int climb(int v, int i) {
        while (true) {
            int L = len.get(v);
            if (i - L - 1 >= 0 && s.charAt(i - L - 1) == s.charAt(i)) return v;
            v = link.get(v);
        }
    }

    void add(char ch) {
        s.append(ch);
        int i = s.length() - 1, c = ch - 'a';
        int v = climb(last, i);
        if (next.get(v)[c] == 0) {
            int suffixLink = len.get(v) + 2 == 1 ? 1 : next.get(climb(link.get(v), i))[c];
            int w = newNode(len.get(v) + 2, suffixLink);
            next.get(v)[c] = w;
        }
        last = next.get(v)[c];
        count.set(last, count.get(last) + 1);
    }

    int distinct() { return len.size() - 2; }

    long totalOccurrences() {
        long[] cnt = new long[len.size()];
        for (int v = 0; v < cnt.length; v++) cnt[v] = count.get(v);
        long total = 0;
        for (int v = cnt.length - 1; v >= 2; v--) { cnt[link.get(v)] += cnt[v]; total += cnt[v]; }
        return total;
    }

    static Eertree build(String s) {
        Eertree t = new Eertree();
        for (char c : s.toCharArray()) t.add(c);
        return t;
    }

    static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }

    public static void main(String[] args) {
        Eertree t = build("eertree");
        check(t.distinct() == 7 && t.totalOccurrences() == 12, "eertree");
        check(build("abacaba").distinct() == 7 && build("aaaa").distinct() == 4, "small");
        check(build("aaaa").totalOccurrences() == 10 && build("").distinct() == 0, "counts");
        Random rng = new Random(1);
        for (int it = 0; it < 3000; it++) {
            int sigma = 1 + rng.nextInt(3), n = rng.nextInt(17);
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) sb.append((char) ('a' + rng.nextInt(sigma)));
            String s = sb.toString();
            Set<String> distinct = new HashSet<>();
            long total = 0;
            for (int i = 0; i < n; i++)
                for (int j = i + 1; j <= n; j++) {
                    String sub = s.substring(i, j);
                    if (new StringBuilder(sub).reverse().toString().equals(sub)) { distinct.add(sub); total++; }
                }
            Eertree e = build(s);
            check(e.distinct() == distinct.size() && e.totalOccurrences() == total, s);
        }
        System.out.println("ok");
    }
}
#include <array>
#include <cassert>
#include <iostream>
#include <random>
#include <set>
#include <string>
#include <vector>

// Palindromic tree. Node 0: imaginary root (length -1). Node 1: empty root (length 0). Lowercase letters only.
struct Eertree {
    std::vector<int> len{-1, 0}, link{0, 0};
    std::vector<long long> count{0, 0};
    std::vector<std::array<int, 26>> next{std::array<int, 26>{}, std::array<int, 26>{}};   // 0 = no edge
    std::string s;
    int last = 1;

    int climb(int v, int i) const {
        while (!(i - len[v] - 1 >= 0 && s[i - len[v] - 1] == s[i])) v = link[v];
        return v;
    }

    void add(char ch) {
        s += ch;
        int i = static_cast<int>(s.size()) - 1, c = ch - 'a';
        int v = climb(last, i);
        if (next[v][c] == 0) {
            int suffixLink = len[v] + 2 == 1 ? 1 : next[climb(link[v], i)][c];
            len.push_back(len[v] + 2);
            link.push_back(suffixLink);
            count.push_back(0);
            next.push_back(std::array<int, 26>{});
            next[v][c] = static_cast<int>(len.size()) - 1;
        }
        last = next[v][c];
        ++count[last];
    }

    int distinct() const { return static_cast<int>(len.size()) - 2; }

    long long totalOccurrences() const {
        std::vector<long long> cnt = count;
        long long total = 0;
        for (int v = static_cast<int>(cnt.size()) - 1; v >= 2; --v) { cnt[link[v]] += cnt[v]; total += cnt[v]; }
        return total;
    }
};

Eertree build(const std::string& s) {
    Eertree t;
    for (char c : s) t.add(c);
    return t;
}

int main() {
    Eertree t = build("eertree");
    assert(t.distinct() == 7 && t.totalOccurrences() == 12);
    assert(build("abacaba").distinct() == 7 && build("aaaa").distinct() == 4);
    assert(build("aaaa").totalOccurrences() == 10 && build("").distinct() == 0);
    std::mt19937 rng(1);
    for (int it = 0; it < 3000; ++it) {
        int sigma = 1 + rng() % 3, n = rng() % 17;
        std::string s;
        for (int i = 0; i < n; ++i) s += static_cast<char>('a' + rng() % sigma);
        std::set<std::string> distinct;
        long long total = 0;
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j <= n; ++j) {
                std::string sub = s.substr(i, j - i);
                if (std::string(sub.rbegin(), sub.rend()) == sub) { distinct.insert(sub); ++total; }
            }
        Eertree e = build(s);
        assert(e.distinct() == static_cast<int>(distinct.size()) && e.totalOccurrences() == total);
    }
    std::cout << "ok\n";
    return 0;
}
/** Palindromic tree. Node 0: imaginary root (length -1). Node 1: empty root (length 0). */
export class Eertree {
  len: number[] = [-1, 0];
  link: number[] = [0, 0];
  count: number[] = [0, 0];
  next: Map<string, number>[] = [new Map(), new Map()];
  s: string[] = [];
  last = 1;

  private climb(v: number, i: number): number {
    while (!(i - this.len[v] - 1 >= 0 && this.s[i - this.len[v] - 1] === this.s[i])) v = this.link[v];
    return v;
  }

  add(c: string): void {
    this.s.push(c);
    const i = this.s.length - 1;
    const v = this.climb(this.last, i);
    if (!this.next[v].has(c)) {
      const suffixLink = this.len[v] + 2 === 1 ? 1 : (this.next[this.climb(this.link[v], i)].get(c) as number);
      this.len.push(this.len[v] + 2);
      this.link.push(suffixLink);
      this.count.push(0);
      this.next.push(new Map());
      this.next[v].set(c, this.len.length - 1);
    }
    this.last = this.next[v].get(c) as number;
    this.count[this.last]++;
  }

  distinct(): number {
    return this.len.length - 2;
  }

  totalOccurrences(): number {
    const cnt = this.count.slice();
    let total = 0;
    for (let v = cnt.length - 1; v >= 2; v--) {
      cnt[this.link[v]] += cnt[v];
      total += cnt[v];
    }
    return total;
  }
}

function build(s: string): Eertree {
  const t = new Eertree();
  for (const c of s) t.add(c);
  return t;
}

const t = build("eertree");
if (t.distinct() !== 7 || t.totalOccurrences() !== 12) throw new Error("eertree");
if (build("abacaba").distinct() !== 7 || build("aaaa").distinct() !== 4) throw new Error("small");
if (build("aaaa").totalOccurrences() !== 10 || build("").distinct() !== 0) throw new Error("counts");
for (let it = 0; it < 3000; it++) {
  const sigma = 1 + Math.floor(Math.random() * 3);
  const n = Math.floor(Math.random() * 17);
  let s = "";
  for (let i = 0; i < n; i++) s += "abc"[Math.floor(Math.random() * sigma)];
  const distinct = new Set<string>();
  let total = 0;
  for (let i = 0; i < n; i++)
    for (let j = i + 1; j <= n; j++) {
      const sub = s.slice(i, j);
      if ([...sub].reverse().join("") === sub) {
        distinct.add(sub);
        total++;
      }
    }
  const e = build(s);
  if (e.distinct() !== distinct.size || e.totalOccurrences() !== total) throw new Error(s);
}
console.log("ok");

The Java and C++ versions use a fixed array of 26 transitions per node (lowercase letters); the Python and TypeScript versions use a map per node and accept any characters. The order "children after their suffix links" holds because a node's suffix link is a shorter palindrome that already existed when the node was created, which is why a single reverse pass over creation order propagates the counts correctly.

Palindromic factorization

A palindromic factorization cuts a string into pieces that are all palindromes; the minimum palindromic factorization uses as few pieces as possible (LeetCode 132 asks for the number of cuts, which is pieces minus one). The standard solution is an DP over prefixes with a palindrome table, covered in String DP and Partition DP. Manacher can replace the table: after computing the radii, enumerate each palindrome by its centre and radius, which visits exactly the palindromic substrings (there can still be of them, so the DP stays quadratic in the worst case, but it needs only memory).

The faster method uses the eertree. The key fact is structural: the lengths of the palindromic suffixes of any string form arithmetic progressions. Store, for each node, the difference between its length and its suffix link's length, plus a "series link" that jumps over a whole progression at once. The DP then processes one progression in amortised, giving for minimum palindromic factorization, online. This was found independently by Fici, Gagie, Kärkkäinen and Kempa (2014) and by I, Sugimoto, Inenaga, Bannai and Takeda (2014), and it is explained with the eertree by Rubinchik and Shur. It is the tool behind Codeforces 932G (see the practice ladder). For interviews, the DP is what you are expected to write.

Real-world uses

Palindromes look like a puzzle topic, but they matter in a few concrete places.

  • Molecular biology: reverse-complement palindromes. In DNA, the meaningful notion is a sequence equal to its own reverse complement (swap A↔T and C↔G, then reverse). Many restriction enzymes cut at such sites: EcoRI recognises GAATTC, whose reverse complement is again GAATTC. Hairpin and stem-loop structures in RNA come from a sequence followed (after a short loop) by its reverse complement. Manacher adapts directly: test " is the complement of " in the even pass (a base is never its own complement, so only even centres apply). Gusfield's textbook (1997, chapter 9) treats finding all maximal complemented palindromes in linear time. The name CRISPR, "clustered regularly interspaced short palindromic repeats", refers to exactly these repeats.
  • Competitive programming and interviews. LeetCode 5 and 647 are among the most frequently asked string problems. Manacher, the eertree and hashing-based palindrome checks are standard pieces of contest libraries; cp-algorithms documents Manacher, and the eertree has been a contest staple since Rubinchik and Shur's 2015 paper.
  • Combinatorics on words. Palindromic richness ("a string is rich if it has the maximum distinct palindromes, counting the empty one") is a studied property of infinite words such as Sturmian words (Glen, Justin, Widmer and Zamboni, 2009). The eertree is the natural tool for experiments on such words.
  • Teaching linear-time amortisation. Manacher, Z and KMP share one proof pattern; learning it once makes the others easy, and it reappears in the suffix automaton and in Ukkonen's suffix-tree construction later in this module.

Pitfalls & edge cases

  • Odd versus even. Forgetting even palindromes is the most common bug: abba has no odd palindrome longer than 1. Either run both passes or use the # transform.
  • Index arithmetic for . The even mirror is , not ; the even box is . Test on abba and aaaa.
  • Box conventions. This lesson's box is inclusive with meaning "none". Versions with exclusive use min(r - i, …). Mixing conventions gives off-by-one errors that only appear on repetitive strings.
  • Recovering the substring. In the # version, the palindrome centred at starts at index of when has no leading sentinel; with the ^ sentinel it is . Write a test that prints the substring, not just the length.
  • Separators that occur in the input. The # transform only needs the separator to be consistent, not absent, because #s only ever face other #s. But the KMP palindromic-prefix trick (s + '#' + rev(s)) does need a separator that cannot occur in ; on arbitrary input, use an integer sentinel.
  • Overflow. The number of palindromic substrings is up to : use 64-bit integers.
  • Empty string and single letters. The longest palindrome of "" is ""; of "x" is "x". Check that your loops handle without reading .
  • Eertree alphabet. Fixed arrays of 26 transitions break on uppercase or digits. Map characters to first, or use maps.
  • Eertree count propagation order. Counts must flow from longer palindromes to their suffix links. Reverse creation order works; sorting by length also works.
  • Unicode. Palindromes of user text should be checked on code points (or grapheme clusters), usually after normalising case and removing punctuation, as LeetCode 125 does.

Variations

  • Longest palindrome after at most one deletion (LeetCode 680): two pointers from the ends; at the first mismatch, try skipping either side. .
  • Palindromes with wildcards or one mismatch. Manacher's reuse breaks when equality is not transitive (wildcards) or when mismatches are allowed. Use hashing plus "kangaroo jumps" (LCP queries) for mismatches per centre: with a suffix-array LCP structure or with hashing.
  • Gapped palindromes (abc + gap + cba): radius computations from each gap position, again with LCP queries.
  • Palindromic substrings in a sliding window or with updates: hashing in a Fenwick tree.
  • Two non-overlapping palindromes with maximum product (LeetCode 1960): Manacher radii plus prefix and suffix maxima.
  • Pal pairs and suffix structures. Palindrome pairs (LeetCode 336) use a hash map or trie of reversed words plus palindromic-prefix/suffix checks. The longest palindromic substring can also be found with a suffix tree or suffix array of (Gusfield, chapter 9), which you will meet in Suffix Arrays & LCP and Suffix Trees.
  • Eertree extensions. Later papers extend the eertree to support undoing the last letter, adding letters at both ends, and persistence; they all keep the "one new node per letter" core.

Practice ladder

Each problem is described in my own words; follow the link for the full statement.

1. Valid Palindrome (LeetCode 125) — Decide whether a sentence is a palindrome after dropping non-alphanumeric characters and ignoring case. Teaches the two-pointer check and input cleaning.

Hint

Two pointers from both ends; skip characters that are not letters or digits; compare lowercased.

2. Valid Palindrome II (LeetCode 680) — Can the string become a palindrome by deleting at most one character? Teaches branching once at the first mismatch.

Hint

At the first mismatch , the answer is whether or is a palindrome.

3. Longest Palindromic Substring (LeetCode 5) — The classic. Teaches expand-around-centre, then Manacher.

Solution

Expand-around-centre is rung 2 above; Manacher is longest_palindrome in the implementation. In an interview, write rung 2 first, state time and space, then describe the mirror trick as the follow-up.

assert longest_palindrome_expand("babad") in ("bab", "aba")
assert longest_palindrome("cbbd") == "bb"

4. Palindromic Substrings (LeetCode 647) — Count all palindromic substrings, by position. Teaches that a radius counts every palindrome at its centre.

Solution
def count_substrings(s):
    d1, d2 = manacher(s)          # from the implementation above
    return sum(d1) + sum(d2)

assert count_substrings("abc") == 3 and count_substrings("aaa") == 6

Each centre with odd radius holds exactly palindromes (lengths ), and each gap with radius holds . .

5. Longest Palindrome (CSES 1111) — Print a longest palindromic substring of a string of up to letters. Teaches Manacher under a limit where is too slow.

Hint

longest_palindrome directly. In Python, read with sys.stdin.readline().strip(); the two passes over letters take about a second or two.

6. Palindrome Partitioning (LeetCode 131) and Palindrome Partitioning II (LeetCode 132) — List every split into palindromes; find the fewest cuts. Teaches the palindrome table feeding backtracking and a 1-D DP.

Hint

Both are worked in full in String DP. For 132 you can drop the table: enumerate palindromes by expanding around each centre and relax cuts[end + 1] from cuts[start] as you go.

7. Shortest Palindrome (LeetCode 214) — Prepend the fewest letters to make a palindrome. Teaches the longest palindromic prefix, three ways.

Solution

shortest_palindrome in the implementation uses Manacher; longest_pal_prefix_kmp above uses KMP. Both run in :

assert shortest_palindrome("aacecaaa") == "aaacecaaa"
s = "aacecaaa"
assert s[longest_pal_prefix_kmp(s):][::-1] + s == "aaacecaaa"

8. Prefix-Suffix Palindrome (Hard version) (Codeforces 1326D2) — Build the longest palindrome of the form (a prefix of ) + (a suffix of ) with total length at most . Teaches peeling matching ends, then a palindromic prefix or suffix of the middle.

Solution

Peel off the longest with equal to the reverse of (match from both ends while letters agree). In the middle part , take the longer of its longest palindromic prefix and its longest palindromic suffix (the suffix is the prefix of ). The answer is + that palindrome + . .

def prefix_suffix_palindrome(s):
    n, k = len(s), 0
    while 2 * k + 1 < n and s[k] == s[n - 1 - k]:
        k += 1
    t = s[k:n - k]
    p = longest_palindromic_prefix(t)          # from the implementation above
    q = longest_palindromic_prefix(t[::-1])
    mid = t[:p] if p >= q else t[len(t) - q:]
    return s[:k] + mid + s[n - k:]

assert prefix_suffix_palindrome("abcdfdcecba") == "abcdfdcba"
assert prefix_suffix_palindrome("abbaxyzyx") == "xyzyx"
assert prefix_suffix_palindrome("codeforces") in ("c", "s")

A brute force over all (prefix, suffix) pairs agreed with this on 2,000 random strings.

9. Palindrome Queries (CSES 2420) — Point updates to a string mixed with "is this range a palindrome?" queries. Teaches the hashing alternative where Manacher cannot follow updates.

Hint

Forward and reverse polynomial hashes stored in two Fenwick trees; see String Hashing, whose practice ladder includes this problem.

10. Maximum Product of the Length of Two Palindromic Substrings (LeetCode 1960) — Choose two non-overlapping odd-length palindromic substrings with the largest product of lengths. Teaches turning radii into "best palindrome ending by position ".

Solution

From , the palindrome centred at with radius ends at with length , and peeling it gives one ending at each earlier position with length 2 less. So: record the full palindromes at their end positions, sweep right to left letting end[i] = max(end[i], end[i + 1] - 2), then take prefix maxima. Do the same mirrored for starts. Answer: .

def max_product(s):
    n = len(s)
    d1, _ = manacher(s)                          # from the implementation above
    def best_by_end(d):
        end = [1] * n
        for c in range(n):
            e = c + d[c] - 1
            end[e] = max(end[e], 2 * d[c] - 1)
        for i in range(n - 2, -1, -1):
            end[i] = max(end[i], end[i + 1] - 2)
        for i in range(1, n):
            end[i] = max(end[i], end[i - 1])
        return end                                # end[i]: longest odd palindrome inside s[0..i]
    pre = best_by_end(d1)
    suf = best_by_end(d1[::-1])[::-1]             # the radii of rev(s) are d1 reversed
    return max(pre[i] * suf[i + 1] for i in range(n - 1))

assert max_product("ababbb") == 9 and max_product("zaaaxbbby") == 9

Checked against a brute force over all pairs of odd palindromes on 2,000 random strings.

11. Palindrome Pairs (LeetCode 336) — Among a list of distinct words, find all ordered pairs whose concatenation is a palindrome. Teaches splitting each word into (palindrome, rest) and looking up the reversed rest.

Hint

For each word and each split point, if the left part is a palindrome, look for a word equal to the reverse of the right part (it goes in front); symmetrically for the right part. Precomputing palindromic prefixes and suffixes of each word with Manacher makes each split check .

12. Palisection (Codeforces 17E) — Count pairs of palindromic substrings (by position) that overlap, modulo a given number, for up to . Teaches turning radii into "how many palindromes start / end at each position" with difference arrays.

Hint

Count all pairs, where = number of palindromic substrings, then subtract non-overlapping pairs: for each position , (palindromes ending at or before ) × (palindromes starting at ). Each centre adds 1 to a contiguous range of start positions and of end positions, so difference arrays over the radii give both counts in .

13. Palindrome Partition (Codeforces 932G) — Count the ways to cut a string into an even number of pieces where piece equals piece . Teaches the interleaving trick and eertree series links.

Hint

Form ; the condition becomes "cut into even-length palindromes". Then run the palindromic factorization DP with the eertree's difference and series links, counting instead of minimising.

Common mistakes & interview follow-ups

"Why is Manacher linear?" Every successful comparison reads a letter to the right of the box, and then the box's right edge moves to cover it. The right edge only moves right and stops at . Each centre adds at most one failed comparison. So at most about comparisons per pass.

"Explain the mirror." The box is a palindrome; reflecting around its centre maps letters to equal letters. The palindrome at the mirror, cut at the box edge, reflects to a palindrome at . Then: inside → equal; sticks out → exactly to the edge; touches → at least to the edge, keep going.

"Odd and even?" Either two arrays with slightly different index arithmetic, or the # transform, which makes every palindrome odd.

"How many distinct palindromes can a string have?" At most non-empty ones, because each new letter creates at most one new palindrome (the longest palindromic suffix). The eertree builds exactly these.

"Substring or subsequence?" Make sure. Longest palindromic subsequence is a different problem ( DP, LCS with the reverse).

"What if the string changes?" Manacher must be rerun. Use hashes in a Fenwick tree for palindrome queries under updates.

Mistakes interviewers watch for: forgetting even-length palindromes; using r - i where the inclusive box needs r - i + 1; wrong mirror for even centres; returning the radius instead of the substring; off-by-one when mapping the # index back to ; int overflow when counting; claiming expand-around-centre is .

Quick quiz

1. Compute and for abba.

Answer

(no odd palindrome longer than one letter) and : the gap before index 2 holds bb and abba. Total palindromic substrings: .

2. In the trace on cbabcbabd, why did centre 6 need only one comparison, even though its mirror had radius 3?

Answer

The mirror's palindrome cbabc sticks out past the box's left edge (case B). So the palindrome at 6 stops exactly at the box's right edge: radius = room = 2. The single comparison, = c against = d, confirms the mismatch that the box's maximality already guaranteed.

3. How many comparisons does Manacher make for both passes on a string of 1,000 as, and how many does expand-around-centre make?

Answer

1,997 against 499,500 (counted by a script). In the odd pass, each centre either copies a radius that runs to the end of the string (no comparison possible) or extends the box; the right edge sweeps the string once.

4. Why can a string of length have at most distinct non-empty palindromes?

Answer

Appending a letter creates new palindromes only among the palindromic suffixes, and every palindromic suffix shorter than the longest one is reflected inside the longest one into an earlier occurrence. So each letter adds at most one new palindrome.

5. In the eertree, why are there two roots instead of one?

Answer

Wrapping a letter around a palindrome adds 2 to the length. To create palindromes of length 2 (cc) we wrap around the empty string (length 0); to create palindromes of length 1 (c) we wrap around an imaginary palindrome of length . The root also ends every suffix-link walk, because its "preceding letter" is the new letter itself.

Further reading / sources

  • Glenn Manacher, "A new linear-time 'on-line' algorithm for finding the smallest initial palindrome of a string", Journal of the ACM 22(3), 1975, pp. 346–351.
  • Alberto Apostolico, Dany Breslauer, Zvi Galil, "Parallel detection of all palindromes in a string", Theoretical Computer Science 141, 1995 (all maximal palindromes from Manacher's idea).
  • Mikhail Rubinchik, Arseny M. Shur, "EERTREE: An efficient data structure for processing palindromes in strings", European Journal of Combinatorics 68, 2018 (conference version IWOCA 2015).
  • Gabriele Fici, Travis Gagie, Juha Kärkkäinen, Dominik Kempa, "A subquadratic algorithm for minimum palindromic factorization", Journal of Discrete Algorithms 28, 2014.
  • Tomohiro I, Shiho Sugimoto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, "Computing palindromic factorizations and palindromic covers on-line", CPM 2014.
  • Xavier Droubay, Jacques Justin, Giuseppe Pirillo, "Episturmian words and some constructions of de Luca and Rauzy", Theoretical Computer Science 255, 2001 (the "at most palindromes" bound); Amy Glen, Jacques Justin, Steve Widmer, Luca Q. Zamboni, "Palindromic richness", European Journal of Combinatorics 30, 2009.
  • Dan Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997, chapter 9 (maximal palindromes and complemented palindromes with suffix trees).
  • cp-algorithms: Manacher's Algorithm (the / convention used here and the # unification).

Previous lesson: Suffix Trees (Ukkonen Intuition) · Next lesson: Minimal Rotation, Lyndon Words & Booth's Algorithm

Related: String Algorithms overview · The Z-Algorithm · KMP & the Prefix Function · String Hashing in Depth · String DP · Sequence DP · Interval DP · Two Pointers · Course home