Skip to content

Palindromic Tree

Definition

The Palindromic Tree (also known as EERTree, Palindromic Automaton) is an efficient data structure for storing all palindromic substrings of a string. It was first introduced by Mikhail Rubinchik and Arseny M. Shur in 2015. Inspired by string suffix data structures like the suffix tree, the Palindromic Tree can simply and efficiently solve a series of problems involving palindromic strings.

Structure

The Palindromic Tree looks roughly like this:

Similar to other automata, the Palindromic Tree consists of transition edges and suffix links (fail pointers). Each node can represent a palindromic substring.

Since palindromic strings can have odd or even lengths, we could add a character not in the character set (like '#') as a separator, similar to Manacher's algorithm, to make all palindromic lengths odd. However, this is overly complicated. Is there a better way?

Naturally, there is. A better approach is to build two trees: one where the nodes correspond to palindromic substrings of odd length, and another where the nodes correspond to palindromic substrings of even length.

Like other automata, a node's fail pointer points to the node representing the longest palindromic suffix of the palindrome represented by this node. However, a transition edge does not represent adding a character after the palindrome represented by the original node, but rather adding the same character to both the front and the back of the palindrome (which is easy to understand, as it ensures the stored string remains a palindrome).

We also need to maintain the length len of the palindromic substring corresponding to each node. This information ensures we can easily construct the Palindromic Tree.

Construction

The Palindromic Tree has two initial states, representing palindromes of length \(-1\) and \(0\), respectively. We can call them the odd root and the even root. They do not represent any actual string but serve as initial states, similar to the root nodes in other automata.

The fail pointer of the even root points to the odd root. We do not care about the fail pointer of the odd root because the odd root can never fail (the next state transitioned from the odd root has length \(1\), i.e., a single character, which is always a palindrome).

Similar to the suffix automaton, we construct the Palindromic Tree incrementally.

Consider constructing the Palindromic Tree for the first \(p-1\) characters, then adding the character at position \(p\) in the original string to the automaton.

We start from the node corresponding to the longest palindromic substring ending with the previous character and repeatedly follow the fail pointer until we find a node satisfying \(s_{p}=s_{p-len-1}\), i.e., the character before the palindrome represented by this node matches the character to be added.

Here is the diagram from the paper:

We find node A by jumping along fail pointers, then add X to both sides to get the current palindrome (XAX). Clearly, this node corresponds to the longest palindromic substring ending at position \(p\). (At this point, the advantage of the length \(-1\) node becomes apparent: if no X matches the condition, the same position \(s_p=s_p\) naturally gives the node representing the character X.) We then need to check: if this node does not exist, we must create it.

Next, we need to determine the fail pointer for the newly created node. The method is similar to the process above: repeatedly jump along fail pointers starting from A to find the longest palindromic suffix of XAX, which is XBX, and set the fail pointer to the corresponding node.

Clearly, this node does not need to be created. The first \(len_B\) characters and the last \(len_B\) characters of A are the same, both being B. The two ends of the first \(len_B\) characters, according to the palindrome correspondence, are both X, and the last character is already determined to be X. Thus, the node XBX must already be included.

If the fail pointer does not match, we link it to the node of length \(0\), which is clearly feasible (since it is a suffix of all nodes).

Proof of Linear Number of States

Theorem

For a string \(s\), the number of distinct palindromic substrings is at most \(|s|\).

Proof

We use mathematical induction.

  • When \(|s| =1\), \(s\) has only one character and only one substring, which is a palindrome. Thus, the conclusion holds.
  • When \(|s| >1\), let \(t=sc\), where \(t\) is the string formed by adding a character \(c\) to the end of \(s\). Assume the conclusion holds for string \(s\). Consider the palindromic substrings ending with the last character \(c\). Suppose their left endpoints, sorted in increasing order, are \(l_1,l_2,\dots,l_k\). Since \(t[l_1..|t|]\) is a palindrome, for all positions \(l_1 \le p \le |t|\), we have \(t[p..|t|]=t[l_1..l_1+|t|-p]\). Therefore, for \(1 < i \le k\), \(t[l_i..|t|]\) has already appeared in \(t[1..|t|-1]\). Thus, each time a character is added, the number of distinct palindromic substrings increases by at most \(1\).

By mathematical induction, the theorem holds.

Therefore, the number of states in the Palindromic Tree is \(O(|s|)\). For each state, it actually represents only one distinct palindromic substring, meaning the transition to this state is unique. Hence, the total number of transitions is also \(O(|s|)\).

Proof of Correctness

Taking the above diagram as an example, when adding the current character X, according to the proof of the linear number of states, we only need to find the longest palindromic suffix containing the last character X, which is XAX. Then, we find the longest palindromic suffix of XAX, which is XBX, and establish the suffix link. The state corresponding to XBX already exists in the Palindromic Tree. The palindromic suffixes containing the last character are XAX, XBX itself, and all ancestors of its corresponding state in the fail tree.

For the construction of the Palindromic Tree for \(s\), let \(n=|s|\). Clearly, operations other than jumping along fail pointers are \(O(n)\).

When adding a character, based on the previous step, each jump along the fail pointer reduces the depth of the corresponding node in the fail tree by \(1\). After linking the fail pointer, the depth only increases by \(1\) (but when fail is \(0\) (i.e., matching only at \(-1\)), the depth effectively increases by \(2\) from \(-1\)).

Since only \(n\) characters are added, the depth increases only \(n\) times, and the fail pointer is jumped at most \(2n\) times.

Therefore, the time complexity of constructing the Palindromic Tree for \(s\) is \(O(|s|)\).

Applications

Number of Distinct Palindromic Substrings

From the proof of the linear number of states, it is easy to see that the number of distinct palindromic substrings of a string equals the number of states in the Palindromic Tree (excluding the two states of the odd and even roots).

Occurrence Count of Palindromic Substrings

Construct the Palindromic Tree and use a method similar to counting occurrences in the suffix automaton.

Since nodes are inserted in topological order during the construction of the Palindromic Tree, we can simply iterate over all states in reverse order and add the occurrence count of the current state to the occurrence count of its fail pointer's target state.

Example Problem: 「APIO2014」Palindromes

Define the existence value of a substring of \(s\) as the product of its occurrence count in \(s\) and its length. For a given string \(s\), find the maximum existence value among all 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 with 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 suffix palindrome
  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 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\) such that there exist \(s_1,s_2,\dots,s_k\), where each \(s_i(1\le i \le k)\) is a palindrome, and the concatenation of \(s_1,s_2, \dots ,s_k\) equals \(s\).

Consider dynamic programming. Let \(dp[i]\) denote the minimum number of partitions for the prefix of \(s\) of length \(i\). The transition only needs to enumerate all palindromes ending with the \(i\)-th character:

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

Since a string can have up to \(O(n^2)\) palindromic substrings, the time complexity of the above algorithm is \(O(n^2)\), which is unacceptable. To optimize the transition process, we present some lemmas.

Let the prefix of string \(s\) of length \(i\) be \(pre(s,i)\), and the suffix of length \(i\) be \(suf(s,i)\).

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

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

Relationship between period and border: \(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|)\). Therefore, \(\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]\). Thus, \(pre(s,|t|)=suf(s,|t|)\), so \(t\) is a border of \(s\).

Lemma 1

\(t\) is a suffix of palindrome \(s\). \(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, we have \(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\), we have \(s[i]=s[|s|-|t|+i]\). Since \(s\) is a palindrome, \(s[i]=s[|s|-i+1]\). Therefore, \(s[|s|-i+1]=s[|s|-|t|+i]\), so \(t\) is a palindrome.

In the figure below, positions with the same color indicate identical characters.

Lemma 2

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

Proof

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

If \(t\) is a palindrome, since \(t\) is a border of \(s\), we have \(\forall 1 \le i \le |t|, s[i]=s[|s|-|t|+i]=s[|s|-i+1]\). Because \(|s| \le 2|t|\), \(s\) is also a palindrome.

Lemma 3

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

Lemma 4

\(x\) is a palindrome, \(y\) is the longest palindromic proper suffix of \(x\), and \(z\) is the longest palindromic proper suffix of \(y\). Let \(u,v\) be strings such that \(x=uy\) and \(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 minimum period of \(x\), and \(|v|=|y|-|z|\) is the minimum period of \(y\). Assume for contradiction that \(|u| < |v|\). Since \(y\) is a suffix of \(x\), \(u\) is both a period of \(x\) and a period of \(y\). However, \(|v|\) is the minimum period of \(y\), leading to a contradiction. Thus, \(|u| \ge |v|\).
  2. Since \(y\) is a border of \(x\), \(v\) is a prefix of \(x\). Let string \(w\) satisfy \(x=vw\) (as shown in the figure below), where \(z\) is a border of \(w\). Assume for contradiction that \(|u| \le |z|\). Then \(|zu| \le 2|z|\), so by Lemma 2, \(w\) is a palindrome. By Lemma 1, \(w\) is a border of \(x\). Since \(|u| > |v|\), we have \(|w| > |y|\), which is a contradiction. Thus, \(|u| > |z|\).
  3. Both \(u\) and \(v\) are prefixes of \(x\), and \(|u|=|v|\), so \(u=v\).

Corollary

All palindromic suffixes of \(s\), when sorted by length, can be partitioned into \(\log |s|\) arithmetic progressions.

Proof

Let the lengths of all palindromic suffixes of \(s\) sorted 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, if \(l_{i}-l_{i-1}\neq l_{i+1}-l_{i}\), by Lemma 4, we have \(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}\). Therefore, if the difference between consecutive pairs of palindromic suffix lengths changes, the maximum length will at least double relative to the minimum length. Clearly, this doubling can occur at most \(O(\log |s|)\) times, meaning the lengths of \(s\)'s palindromic suffixes can be partitioned into \(\log |s|\) arithmetic progressions.

This corollary can also be proven using the Weak Periodicity Lemma, classifying all borders of \(s\)'s longest palindromic suffix by length \(x\) into intervals \([2^0,2^1),[2^1,2^2),\dots,[2^k,n)\), and considering the longest border in each of these \(\log |s|\) groups. For a detailed proof, refer to Jin Ce's "Selected Topics in String Algorithms" and Chen Sunli's 2019 IOI National Team Candidate Paper "Algorithms for Substring Period Queries and Their Applications".

With this conclusion, we can now consider how to optimize the DP transitions.

Optimization

Each node \(u\) in the Palindromic Tree needs to maintain two additional pieces of information: \(diff[u]\) and \(slink[u]\). \(diff[u]\) represents the length difference between the palindrome represented by node \(u\) and its fail node, i.e., \(len[u]-len[fail[u]]\). \(slink[u]\) denotes the first node \(v\) reached by repeatedly following fail pointers from \(u\) such that \(diff[v] \neq diff[u]\), i.e., the node with the smallest length in the arithmetic progression containing \(u\).

According to the proven conclusion, using the \(slink\) pointer to jump upward, only \(O(\log |s|)\) jumps are needed for each character added. Therefore, we can consider summing the DP values (in the original problem, the \(\min\) values) of all palindromes represented by an arithmetic progression and recording them on the node corresponding to the longest palindrome in that progression.

Let \(g[v]\) denote the sum of DP values for the arithmetic progression containing \(v\), where \(v\) is the node with the longest length in this progression. Then \(g[v]=\sum_{slink[x]=slink[v]} dp[i-len[x]]\), where \(i\) is the current index being enumerated.

Now, consider how to update the \(g\) array and the \(dp\) array. As shown in the figure below, suppose the current enumeration is at the \(i\)-th character, and the corresponding node in the Palindromic Tree is \(x\). \(g[x]\) is the sum of DP values at the three orange positions (the shortest palindrome \(slink[x]\) is counted in the next arithmetic progression). The last occurrence of \(fail[x]\) is at position \(i-diff[x]\) (ending at \(i-diff[x]\)), and \(g[fail[x]]\) contains the DP values at the blue positions. Therefore, \(g[x]\) actually equals \(g[fail[x]]\) plus the DP value at one additional position: \(i-(len[slink[x]]+diff[x])\). Finally, use \(g[x]\) to update \(dp[i]\), completing the calculation of contributions from this arithmetic progression. Repeat this process by repeatedly jumping to \(slink[x]\). For implementation details, refer to the example code.

The correctness of the above approach relies on the following: if \(x\) and \(fail[x]\) belong to the same arithmetic progression, then the last occurrence of \(fail[x]\) is at \(i-diff[x]\).

Proof

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

Assume \(fail[x]\) appears at position \(j\) in \((i-diff[x],i)\). Since \(x\) and \(fail[x]\) belong to the same arithmetic progression, we have \(2|fail[x]| \ge x\). The extra \(fail[x]\) and the \(fail[x]\) at \(i-diff[x]\) overlap. Let the overlap be \(w\), and let string \(u\) satisfy \(uw=fail[x]\). Using a method similar to Lemma 1, we can prove that \(w\) is a palindrome, and the prefix of \(x\), \(s[i-len[x]+1..j]=uwu\), is also a palindrome. This contradicts the fact that \(fail[x]\) is the longest palindromic prefix (suffix) of \(x\).

Example Problem: 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 such partition schemes.

Solution

Construct 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 equivalent to finding the number of even palindromic partitions of \(t\). Modify the transition equation to a summation form and update the \(dp\) array only at even positions. Time complexity: \(O(n \log n)\), space complexity: \(O(n)\).

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 with 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 suffix palindrome
  while (s[tot - len[x] - 1] != s[tot]) x = fail[x];
  return x;
}

void insert(char c) {  // Build 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 dp array at even positions
    }
  }
  cout << dp[n];
  return 0;
}

Example Problems

References

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