Skip to content

Palindromic Tree

Definition

The palindromic tree (also known as the eertree or the palindromic automaton) is an efficient data structure that stores all palindromic substrings of a string. It was first published by Mikhail Rubinchik and Arseny M. Shur in 2015. It was inspired by suffix data structures for strings such as the suffix tree, and it solves a whole range of problems about palindromes simply and efficiently.

Structure

A palindromic tree looks roughly like this:

Like other automata, a palindromic tree is made of transition edges and suffix links (failure links), and every node represents a palindromic substring.

Palindromes have either odd or even length. We could do as in Manacher's algorithm and insert a character outside the alphabet (such as '#') as a separator, so that every palindrome has odd length, but that is too much trouble. Is there a better way?

Of course there is: build two trees. In one, every node corresponds to a palindromic substring of odd length; in the other, every node corresponds to one of even length.

As in other automata, the failure link of a node points to the node for the longest palindromic suffix of the palindrome that the node represents. A transition edge, however, does not append one character to the palindrome of the node it leaves: it adds the same character at both ends of that palindrome (naturally, since what we store has to be a palindrome).

Each node also stores the length len of its palindromic substring. With this information the palindromic tree is easy to construct.

Construction

A palindromic tree has two initial states, which represent palindromes of length \(-1\) and \(0\). We call them the odd root and the even root. They do not stand for any actual string and exist only as initial states, just like the root node of other automata.

The failure link of the even root points to the odd root. We do not care about the failure link of the odd root, because a mismatch cannot happen at the odd root (a transition out of the odd root leads to a state of length \(1\), a single character, which is always a palindromic substring).

As with the suffix automaton, we construct the palindromic tree incrementally.

Suppose the palindromic tree of the first \(p-1\) characters has been built, and we now add to the automaton the character at position \(p\) of the original string.

Start from the node of the longest palindromic substring that ends at the previous character and keep following failure links until you reach a node with \(s_{p}=s_{p-len-1}\), that is, a node whose palindromic substring is preceded by the same character as the one being added.

Here is the figure from the paper:

Following failure links, we find the node of A; adding X at both ends takes us to the current palindrome (namely XAX). Clearly this is the node of the tree for the longest palindromic substring ending at \(p\). (This is also where the node of length \(-1\) shows its worth: if there is no matching X, the condition becomes \(s_p=s_p\), one position compared with itself, and we arrive naturally at the node for the single character X.) At this point we have to check: if this node does not exist yet, create it.

We also need the failure link of the newly created node. The method is like the one above: starting from A, keep following failure links to find XBX, the longest palindromic suffix of XAX, and make the failure link point to its node.

Clearly this node never has to be created. The first \(len_B\) characters and the last \(len_B\) characters of A are the same: both are B. Because XAX is a palindrome, the first copy has X at both ends, and the character after the last copy is X by the choice of A; so the node XBX must already be there.

If no match is found for the failure link, point it to the node of length \(0\). This is clearly valid (because it is a suffix of every node).

Proof that the number of states is linear

Theorem

A string \(s\) has at most \(|s|\) distinct palindromic substrings.

Proof

We use mathematical induction.

  • When \(|s| =1\), \(s\) has a single character and hence a single substring, which is a palindrome, so the claim holds.

  • When \(|s| >1\), let \(t=sc\), where \(t\) is the string obtained by appending a character \(c\) to \(s\), and assume the claim holds for \(s\). Consider the palindromic substrings that end at the last character \(c\), and let their left endpoints in increasing order be \(l_1,l_2,\dots,l_k\). Since \(t[l_1..|t|]\) is a palindrome, \(t[p..|t|]=t[l_1..l_1+|t|-p]\) for every position \(l_1 \le p \le |t|\). So for \(1 < i \le k\), \(t[l_i..|t|]\) already occurs in \(t[1..|t|-1]\). Hence each added character increases the number of distinct palindromic substrings by at most \(1\).

By mathematical induction, the theorem holds.

So a palindromic tree has \(O(|s|)\) states. Each state in fact represents exactly one distinct palindromic substring, so only one state has a transition into it; the total number of transitions is therefore \(O(|s|)\) as well.

Proof of correctness

Take the figure above as an example and add the current character X. By the proof that the number of states is linear, we only need to find the longest palindromic suffix that contains the last character X, which is XAX. We then go on to find XBX, the longest palindromic suffix of XAX, and set the suffix link. The state of XBX is already in the palindromic tree, and the palindromic suffixes that contain the last character are XAX, XBX itself, and all the ancestors of its state in the failure tree.

For the construction of the palindromic tree of \(s\), let \(n=|s|\). Clearly everything other than following failure links takes \(O(n)\).

When a character is added, we continue from where the previous one left off. Each jump along a failure link changes the depth of the current node in the failure tree by \(-1\), and setting the new failure link afterwards raises the depth by only 1 (except that when the failure link is the node of length \(0\), which means that only the node of length \(-1\) matched, the depth is in effect \(+2\) relative to that of the node of length \(-1\)).

Only \(n\) characters are added, so the depth increases only \(n\) times, and failure links are followed at most \(2n\) times.

So the palindromic tree of \(s\) is built in \(O(|s|)\) time.

Applications

Number of distinct palindromic substrings

By the proof that the number of states is linear, the number of distinct palindromic substrings of a string equals the number of states of its palindromic tree (not counting the odd root and the even root).

Number of occurrences of palindromic substrings

Build the palindromic tree and count occurrences in much the same way as with a suffix automaton.

During the construction of the palindromic tree the nodes are already inserted in topological order, so it is enough to iterate over all states in reverse order and add the occurrence count of the current state to that of the state its failure link points to.

Example: [APIO2014] Palindromes

Define the occurrence value of a substring of \(s\) as the number of times it occurs in \(s\) multiplied by its length. Given a string \(s\), find the maximum occurrence value among all its palindromic substrings.

Reference code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <algorithm>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
constexpr int MAXN = 300000 + 5;

namespace pam {
int sz, tot, last;
int cnt[MAXN], ch[MAXN][26], len[MAXN], fail[MAXN];
char s[MAXN];

int node(int l) {  // create a new node of length l
  sz++;
  memset(ch[sz], 0, sizeof(ch[sz]));
  len[sz] = l;
  fail[sz] = cnt[sz] = 0;
  return sz;
}

void clear() {  // initialize
  sz = -1;
  last = 0;
  s[tot = 0] = '$';
  node(0);
  node(-1);
  fail[0] = 1;
}

int getfail(int x) {  // find the palindromic suffix
  while (s[tot - len[x] - 1] != s[tot]) x = fail[x];
  return x;
}

void insert(char c) {  // build the tree
  s[++tot] = c;
  int now = getfail(last);
  if (!ch[now][c - 'a']) {
    int x = node(len[now] + 2);
    fail[x] = ch[getfail(fail[now])][c - 'a'];
    ch[now][c - 'a'] = x;
  }
  last = ch[now][c - 'a'];
  cnt[last]++;
}

long long solve() {
  long long ans = 0;
  for (int i = sz; i >= 0; i--) {
    cnt[fail[i]] += cnt[i];
  }
  for (int i = 1; i <= sz; i++) {  // update the answer
    ans = max(ans, 1ll * len[i] * cnt[i]);
  }
  return ans;
}
}  // namespace pam

string s;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  pam::clear();
  cin >> s;
  for (int i = 0; i < s.size(); i++) {
    pam::insert(s[i]);
  }
  cout << pam::solve() << '\n';
  return 0;
}

Minimum palindromic partition

Given a string \(s(1\le |s| \le 10^5)\), find the smallest \(k\) for which there exist \(s_1,s_2,\dots,s_k\) such that every \(s_i(1\le i \le k)\) is a palindrome and concatenating \(s_1,s_2, \dots ,s_k\) in order gives \(s\).

Use dynamic programming. Let \(dp[i]\) be the minimum number of parts in a partition of the prefix of \(s\) of length \(i\). The transition only has to enumerate all palindromes that end at the \(i\)-th character:

\[ dp[i]=1+\min_{ s[j+1..i] \text{ is a palindrome} } dp[j] \]

A string can have up to \(O(n^2)\) palindromic substrings, so this algorithm runs in \(O(n^2)\), which is too slow. To optimize the transition, we first need a few lemmas.

Write \(pre(s,i)\) for the prefix of length \(i\) of a string \(s\), and \(suf(s,i)\) for its suffix of length \(i\).

Period: if \(0< p \le |s|\) and \(\forall 1 \le i \le |s|-p,s[i]=s[i+p]\), then \(p\) is called a period of \(s\).

Border: if \(0 \le r < |s|\) and \(pre(s,r)=suf(s,r)\), then \(pre(s,r)\) is called a border of \(s\).

Periods and borders are related as follows: \(t\) is a border of \(s\) if and only if \(|s|-|t|\) is a period of \(s\).

Proof

If \(t\) is a border of \(s\), then \(pre(s,|t|)=suf(s,|t|)\), hence \(\forall 1\le i \le |t|, s[i]=s[|s|-|t|+i]\), so \(|s|-|t|\) is a period of \(s\).

If \(|s|-|t|\) is a period of \(s\), then \(\forall 1 \le i \le |s|-(|s|-|t|)=|t|,s[i]=s[|s|-|t|+i]\), hence \(pre(s,|t|)=suf(s,|t|)\), so \(t\) is a border of \(s\).

Lemma 1

Let \(t\) be a suffix of a palindrome \(s\). Then \(t\) is a border of \(s\) if and only if \(t\) is a palindrome.

Proof

For \(1 \le i \le |t|\): since \(s\) and \(t\) are palindromes, \(s[i]=s[|s|-i+1]=s[|s|-|t|+i]\), so \(t\) is a border of \(s\).

For \(1 \le i \le |t|\): since \(t\) is a border of \(s\), \(s[i]=s[|s|-|t|+i]\); since \(s\) is a palindrome, \(s[i]=s[|s|-i+1]\). Hence \(s[|s|-i+1]=s[|s|-|t|+i]\), so \(t\) is a palindrome.

In the figure below, positions of the same color hold the same character.

Lemma 2

Let \(t\) be a border of a string \(s\) (\(|s|\le 2|t|\)). Then \(s\) is a palindrome if and only if \(t\) is a palindrome.

Proof

If \(s\) is a palindrome, then by Lemma \(1\) so is \(t\).

If \(t\) is a palindrome, then since \(t\) is a border of \(s\), \(\forall 1 \le i \le |t|, s[i]=s[|s|-|t|+i]=s[|s|-i+1]\); because \(|s| \le 2|t|\), \(s\) is a palindrome too.

Lemma 3

Let \(t\) be a border of a palindrome \(s\). Then \(|s|-|t|\) is a period of \(s\), and \(|s|-|t|\) is the smallest period of \(s\) if and only if \(t\) is the longest proper palindromic suffix of \(s\).

Lemma 4

Let \(x\) be a palindrome, \(y\) the longest proper palindromic suffix of \(x\), and \(z\) the longest proper palindromic suffix of \(y\). Let \(u\) and \(v\) be the strings such that \(x=uy,y=vz\). Then the following three properties hold:

  1. \(|u| \ge |v|\);

  2. if \(|u| > |v|\), then \(|u| > |z|\);

  3. if \(|u| = |v|\), then \(u=v\).

Proof
  1. By the corollary of Lemma \(3\), \(|u|=|x|-|y|\) is the smallest period of \(x\) and \(|v|=|y|-|z|\) is the smallest period of \(y\). Proof by contradiction: suppose \(|u| < |v|\). Since \(y\) is a suffix of \(x\), \(|u|\) is a period of \(y\) as well as of \(x\); but \(|v|\) is the smallest period of \(y\), a contradiction. So \(|u| \ge |v|\).
  2. Since \(y\) is a border of \(x\), \(v\) is a prefix of \(x\). Let \(w\) be the string with \(x=vw\) (see the figure below); then \(z\) is a border of \(w\). Again by contradiction: suppose \(|u| \le |z|\). Then \(|zu| \le 2|z|\), so \(w\) is a palindrome by Lemma \(2\) and hence a border of \(x\) by Lemma \(1\). But \(|u| > |v|\) gives \(|w| > |y|\), a contradiction. So \(|u| > |z|\).
  3. Both \(u\) and \(v\) are prefixes of \(x\) and \(|u|=|v|\), so \(u=v\).

Corollary

Sorted by length, the palindromic suffixes of \(s\) can be partitioned into \(\log |s|\) arithmetic progressions.

Proof

Let the lengths of all palindromic suffixes of \(s\), in increasing order, be \(l_1,l_2,\dots,l_k\). For any \(2 \le i \le k-1\), if \(l_{i}-l_{i-1}=l_{i+1}-l_{i}\), then \(l_{i-1},l_{i},l_{i+1}\) form an arithmetic progression. Otherwise \(l_{i}-l_{i-1}\neq l_{i+1}-l_{i}\), and Lemma \(4\) gives \(l_{i+1}-l_{i}>l_{i}-l_{i-1}\) and \(l_{i+1}-l_{i}>l_{i-1}\), so \(l_{i+1}>2l_{i-1}\). So whenever the difference between consecutive lengths changes from one pair of palindromic suffixes to the next, the largest of these lengths is more than double the smallest. Clearly the length can double at most \(O(\log |s|)\) times, which means that the lengths of the palindromic suffixes of \(s\) can be partitioned into \(\log |s|\) arithmetic progressions.

The corollary can also be proved with the weak periodicity lemma: classify all borders of the longest palindromic suffix of \(s\) by their length \(x\), with \(x \in [2^0,2^1),[2^1,2^2),\dots,[2^k,n)\), and consider the longest border in each of these \(\log |s|\) groups. For a detailed proof, see Ce Jin's Selected Topics in String Algorithms and Sunli Chen's 2019 IOI national team candidates paper Algorithms for Substring Period Queries and Their Applications (both in Chinese).

With this result in hand, we can now look at how to optimize the \(dp\) transition.

Optimization

Each node \(u\) of the palindromic tree stores two more values, \(diff[u]\) and \(slink[u]\). \(diff[u]\) is the difference between the lengths of the palindromes represented by \(u\) and by \(fail[u]\), that is, \(len[u]-len[fail[u]]\). \(slink[u]\) is the first node \(v\) with \(diff[v] \neq diff[u]\) that is reached by following failure links upward from \(u\); in other words, it is the shortest node of the arithmetic progression that \(u\) belongs to.

By the result proved above, if we jump upward along \(slink\) pointers, each appended character needs only \(O(\log |s|)\) jumps. So we can store the sum of the \(dp\) values of all the palindromes of one arithmetic progression (in the original problem, read \(\min\) for sum) at the node of the longest of these palindromes.

Let \(g[v]\) be the sum of the \(dp\) values of the arithmetic progression that contains \(v\), where \(v\) is the longest node of that progression. Then \(g[v]=\sum_{slink[x]=slink[v]} dp[i-len[x]]\), where \(i\) is the index currently being processed.

Now let us see how to update the arrays \(g\) and \(dp\). Take the figure below as an example. Suppose we are at the \(i\)-th character and the corresponding node of the palindromic tree is \(x\). \(g[x]\) is the sum of the \(dp\) values at the three orange positions (the shortest palindrome, \(slink[x]\), is counted in the next arithmetic progression). The previous occurrence of \(fail[x]\) is at \(i-diff[x]\) (it ends at \(i-diff[x]\)), and the \(dp\) values included in \(g[fail[x]]\) are those at the blue positions. So \(g[x]\) is in fact \(g[fail[x]]\) plus the \(dp\) value at one extra position, namely \(i-(len[slink[x]]+diff[x])\). Finally, use \(g[x]\) to update \(dp[i]\); that completes the contribution of this arithmetic progression. Keep jumping to \(slink[x]\) and repeat. For the implementation details, see the code of the example problem.

Finally, the correctness of this method rests on the following fact: if \(x\) and \(fail[x]\) belong to the same arithmetic progression, then the previous occurrence of \(fail[x]\) is at \(i-diff[x]\).

Proof

By Lemma \(1\), \(fail[x]\) is a border of \(x\), so it occurs at \(i-diff[x]\).

Suppose \(fail[x]\) also occurs at a position \(j\) in \((i-diff[x],i)\). Since \(x\) and \(fail[x]\) belong to the same arithmetic progression, \(2|fail[x]| \ge |x|\). The extra occurrence of \(fail[x]\) overlaps the one at \(i-diff[x]\); call their intersection \(w\), and let \(u\) be the string with \(uw=fail[x]\). An argument like that of Lemma \(1\) shows that \(w\) is a palindrome, and then the prefix \(s[i-len[x]+1..j]=uwu\) of \(x\) is a palindrome as well, which contradicts the fact that \(fail[x]\) is the longest palindromic prefix (suffix) of \(x\).

Example: Codeforces 932G Palindrome Partition

Given a string \(s\), partition it into \(t_1, t_2, \dots, t_k\), where \(k\) is even and \(t_i=t_{k-i+1}\). Find the number of ways to do this.

Solution

Construct the string \(t= s[0]s[n - 1]s[1]s[n - 2]s[2]s[n - 3] \dots s[n / 2 - 1]s[n / 2]\). The problem is then equivalent to counting the partitions of \(t\) into even-length palindromes: turn the transition above into a sum and update the \(dp\) array only at even positions. This takes \(O(n \log n)\) time and \(O(n)\) space.

Reference code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
using ll = long long;
constexpr int mod = 1e9 + 7;
constexpr int MAXN = 1000000 + 5;

int add(int x, int y) {
  x += y;
  return x >= mod ? x -= mod : x;
}

namespace pam {
int sz, tot, last;
int ch[MAXN][26], len[MAXN], fail[MAXN];
int cnt[MAXN], dep[MAXN], dif[MAXN], slink[MAXN];
char s[MAXN];

int node(int l) {  // create a new node of length l
  sz++;
  memset(ch[sz], 0, sizeof(ch[sz]));
  len[sz] = l;
  fail[sz] = 0;
  cnt[sz] = 0;
  dep[sz] = 0;
  return sz;
}

void clear() {  // initialize
  sz = -1;
  last = 0;
  s[tot = 0] = '$';
  node(0);
  node(-1);
  fail[0] = 1;
}

int getfail(int x) {  // find the palindromic suffix
  while (s[tot - len[x] - 1] != s[tot]) x = fail[x];
  return x;
}

void insert(char c) {  // build the tree
  s[++tot] = c;
  int now = getfail(last);
  if (!ch[now][c - 'a']) {
    int x = node(len[now] + 2);
    fail[x] = ch[getfail(fail[now])][c - 'a'];
    dep[x] = dep[fail[x]] + 1;
    ch[now][c - 'a'] = x;
    dif[x] = len[x] - len[fail[x]];
    if (dif[x] == dif[fail[x]])
      slink[x] = slink[fail[x]];
    else
      slink[x] = fail[x];
  }
  last = ch[now][c - 'a'];
  cnt[last]++;
}
}  // namespace pam

using pam::dif;
using pam::fail;
using pam::len;
using pam::slink;
int n, dp[MAXN], g[MAXN];
string s;
char t[MAXN];

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  pam::clear();
  cin >> s;
  n = s.size();
  s = " " + s;
  for (int i = 1, j = 0; i <= n; i++) t[++j] = s[i], t[++j] = s[n - i + 1];
  dp[0] = 1;
  for (int i = 1; i <= n; i++) {
    pam::insert(t[i]);
    for (int x = pam::last; x > 1; x = slink[x]) {
      g[x] = dp[i - len[slink[x]] - dif[x]];
      if (dif[x] == dif[fail[x]]) g[x] = add(g[x], g[fail[x]]);
      if (i % 2 == 0) dp[i] = add(dp[i], g[x]);  // update the dp array at even positions
    }
  }
  cout << dp[n];
  return 0;
}

Example problems