AIOJ

Definition

A palindromic tree (EER tree, also called a 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. Inspired by suffix trees and other suffix-oriented string structures, it gives simple and efficient solutions to many palindrome problems.

Structure

A palindromic tree looks roughly like this.

As with other automata, a palindromic tree consists of transition edges and suffix links (fail pointers), and each node represents a palindromic substring.

Because palindromes can have odd or even length, one could insert a character outside the alphabet, such as '#', as a separator, as in Manacher's algorithm, so that all palindrome lengths become odd. This is inconvenient, however. Is there a better method?

Yes. Build two trees: nodes in one tree represent palindromes of odd length, and nodes in the other represent palindromes of even length.

As in other automata, a node's fail pointer points to the node representing the longest palindromic suffix of its palindrome. A transition edge does not append one character to the original palindrome; it adds the same character to both ends, which is necessary to preserve palindromicity.

Each node also stores len, the length of its palindrome. This information makes the tree easy to construct.

Construction

A palindromic tree has two initial states representing palindromes of lengths $-1,0$ , called the odd root and even root. They do not represent actual strings; they only serve as initial states, just like roots of other automata.

The even root's fail pointer points to the odd root. The odd root's fail pointer is irrelevant: the odd root cannot fail, because every transition from it has length $1$ , a single-character palindrome.

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

Suppose the tree for the first $p-1$ characters has been built, and we append the character at position $p$ of the original string.

Starting from the node representing the longest palindromic suffix ending at the previous character, repeatedly follow fail pointers until finding a node satisfying $s_{p}=s_{p-len-1}$ ; that is, the character immediately before the represented palindrome equals the character being appended.

Here is the corresponding figure from the paper.

Following fail pointers finds the node for A; adding X to both ends gives the current palindrome XAX. This node is the tree node for the longest palindromic suffix ending at $p$ . The length- $-1$ node is useful here: if no X matches, the condition reduces to $s_p=s_p$ , so the node representing the one-character palindrome X is obtained naturally. The pair X and XAX is therefore handled by the same transition. If this node does not yet exist, create it.

We must then find the fail pointer of the new node. Again follow fail pointers from A to find the longest palindromic suffix XBX of XAX, and set the fail pointer to its node.

This node never needs to be created: the first $len_B$ characters and last $len_B$ characters of A are both B; the two ends of the first part correspond to X by palindromicity, and the second part is fixed as X, so the same $len_B$ -length construction gives XBX, which must already be present.

If no fail transition matches, connect the node to the length- $0$ node, which is valid because the empty string is a suffix of every node.

Proof of the linear number of states

Theorem

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

Proof

Use mathematical induction.

If $|s| =1$ , the string $s$ has one character and one substring, which is a palindrome, so the claim holds.
If $|s| >1$ , let $t=sc$ , where $t$ is obtained by appending $c$ to $s$ , and assume the claim holds for $s$ . Consider palindromic substrings ending at the final character $c$ , and sort their left endpoints as $l_1,l_2,\dots,l_k$ . Since $t[l_1..|t|]$ is a palindrome, for every $l_1 \le p \le |t|$ we have $t[p..|t|]=t[l_1..l_1+|t|-p]$ . Hence, for $1 < i \le k$ , the palindrome $t[l_i..|t|]$ already occurred in $t[1..|t|-1]$ . Each appended character therefore introduces at most one new distinct palindrome, and the first such position is $1$ .

By induction, the theorem follows.

Thus the palindromic tree has $O(|s|)$ states. Each state represents exactly one distinct palindrome, and the state that transitions to a node is unique, so the total number of transitions is also $O(|s|)$ .

Correctness proof

In the figure above, when the current character X is added, the linear-state proof says that we only need to find the longest palindromic suffix containing the final character, namely XAX. We then find its longest palindromic suffix XBX and create the suffix link. The state for XBX already exists; its palindromic suffix containing the final character is XAX, and XBX itself and all ancestors of its state in the fail tree are therefore already represented.

For the palindromic tree of $s$ , let $n=|s|$ . Apart from following fail pointers, all operations are clearly $O(n)$ .

When a character is added, each fail jump changes the fail-tree depth by $-1$ , while adding a fail link changes it by $-1$ in the accounting below. When fail is $0$ , reaching $-1$ , the net increase is $+2$ from the negative-one node.

Only $n$ characters are added, so the depth can increase at most $n$ times and there can be at most $2n$ fail jumps.

Therefore, constructing the palindromic tree of $s$ takes $O(|s|)$ time.

Applications

Number of distinct palindromic substrings

By the linear-state theorem, the number of distinct palindromic substrings of a string equals the number of palindromic-tree states, excluding the odd and even roots.

Number of occurrences of palindromic substrings

Build the palindromic tree and count occurrences similarly to a suffix automaton.

Nodes are inserted in topological order during construction. Enumerate all states in reverse order and add each state's occurrence count to the count of the state pointed to by its fail link.

Example: 「APIO2014」Palindrome

Define the existence value of a substring of $s$ as its number of occurrences in $s$ multiplied by its length. Given $s$ , find the maximum existence value among its palindromic substrings.

#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 a 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 minimum $k$ such that there are strings $s_1,s_2,\dots,s_k$ , each $s_i(1\le i \le k)$ a palindrome, whose concatenation $s_1,s_2, \dots ,s_k$ in order equals $s$ .

Consider DP, where $dp[i]$ is the minimum number of parts for the length- $i$ prefix of $s$ . The transition enumerates all palindromes ending at character $i$ :

dp[i]=1+\min_{ s[j+1..i] \text{ 为回文串} } dp[j]

There can be $O(n^2)$ palindromic substrings, so this takes $O(n^2)$ time and is too slow. The following lemmas optimize the transition.

Let the prefix of $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$ .

Relation between periods and borders: $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|)$ , so $\forall 1\le i \le |t|, s[i]=s[|s|-|t|+i]$ . Hence $|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]$ , so $pre(s,|t|)=suf(s,|t|)$ and $t$ is a border of $s$ .

Lemma 1

For a palindromic string $s$ and a suffix $t$ of the string, the suffix $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$ .

Conversely, for $1 \le i \le |t|$ , if $t$ is a border of $s$ , $s[i]=s[|s|-|t|+i]$ . Since $s$ is a palindrome, the same string gives $s[i]=s[|s|-i+1]$ , hence $s[|s|-i+1]=s[|s|-|t|+i]$ and $t$ is a palindrome.

The positions with the same color in the figure represent equal characters.

Lemma 2

Let $t$ be a border of $s$ with $|s|\le 2|t|$ . Then $s$ is a palindrome if and only if $t$ is a palindrome.

Proof

If $s$ is a palindrome, Lemma $1$ shows that the suffix $t$ and this $s$ are also palindromes.

If $t$ is a palindrome, this $t$ has the border relation $\forall 1 \le i \le |t|, s[i]=s[|s|-|t|+i]=s[|s|-i+1]$ . Since $|s| \le 2|t|$ , $s$ is also a palindrome.

Lemma 3

If $t$ is a border of a palindromic string, then $|s|-|t|$ is a period of $s$ . It is the minimum period $|s|-|t|$ of $s$ if and only if $t$ is the longest proper palindromic suffix of $s$ ; both quantities refer to $s$ .

Lemma 4

Let $x$ be a palindrome, and let $y$ be the longest proper palindromic suffix of $x$ ; let $z$ be the longest proper palindromic suffix of $y$ . Let $u,v$ satisfy $x=uy,y=vz$ . Then:

$|u| \ge |v|$ ;
If $|u| > |v|$ , then $|u| > |z|$ ;
If $|u| = |v|$ , then $u=v$ .

Proof

By the consequence of Lemma $3$ , $|u|=|x|-|y|$ is the minimum period of $x$ , and $|v|=|y|-|z|$ is the minimum period of $y$ . If $|u| < |v|$ , then, because $y$ is a suffix of $x$ , $u$ is a period of both $x$ and $y$ , contradicting the minimality of $|v|$ for $y$ . Thus $|u| \ge |v|$ .
Since $y$ is a border of $x$ , $v$ is a prefix of $x$ . Write $x=vw$ , so $z$ is a border of $w$ . If $|u| \le |z|$ , then $|zu| \le 2|z|$ ; Lemma $2$ makes $w$ a palindrome, and Lemma $1$ makes $w$ a border of $x$ . Since $|u| > |v|$ , this gives $|w| > |y|$ , a contradiction. Therefore $|u| > |z|$ , with the same $w$ notation.
Both $u,v$ are prefixes of $x$ and have $|u|=|v|$ , so $u=v$ .

Corollary

When all palindromic suffixes of $s$ are sorted by length, they can be divided into $\log |s|$ arithmetic-progression segments.

Proof

Sort the lengths of the palindromic suffixes of $s$ increasingly as $l_1,l_2,\dots,l_k$ . For $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}$ . Whenever the difference changes, the largest length therefore more than doubles relative to the smallest. This can happen only $O(\log |s|)$ times, so the lengths of the palindromic suffixes of $s$ form $\log |s|$ arithmetic-progression segments.

The corollary can also be proved with the weak periodicity lemma by grouping the borders of the longest palindromic suffix $s$ according to their length $x$ , where $x \in [2^0,2^1),[2^1,2^2),\dots,[2^k,n)$ . Considering the longest border in each group gives $\log |s|$ groups. Detailed proofs can be found in Jin Ce's Selected String Algorithms and Chen Sunli's 2019 IOI National Candidate Team paper Algorithms and Applications for Substring Period Queries.

With this result, we can optimize the transition of $dp$ .

Optimization

For every node $u$ in the palindromic tree, maintain $diff[u]$ and $slink[u]$ . Here $diff[u]$ is the difference between the lengths represented by $u$ and $fail[u]$ , namely $len[u]-len[fail[u]]$ . The pointer $slink[u]$ follows fail pointers from $u$ to the first node $v$ with $diff[v] \neq diff[u]$ ; it is the shortest-length node in the arithmetic-progression segment containing $u$ .

By the result above, following $slink$ requires only $O(\log |s|)$ jumps for each appended character. We can therefore store the sum of the $dp$ values of all palindromes in one arithmetic-progression segment (the original problem uses $\min$ ) at the node representing its longest palindrome.

Let $g[v]$ be the sum of the $dp$ values in the arithmetic-progression segment containing $v$ , where $v$ is its longest node. Then $g[v]=\sum_{slink[x]=slink[v]} dp[i-len[x]]$ , with $i$ the current index.

To update $g$ and $dp$ , suppose the current character is at index $i$ and its palindromic-tree node is $x$ . The orange positions in the figure contribute to $g[x]$ ; the shortest palindrome $slink[x]$ belongs to the next segment. The previous occurrence of $fail[x]$ ends at $i-diff[x]$ , and $g[fail[x]]$ contains the blue $dp$ values. Thus $g[x]$ is $g[fail[x]]$ plus one additional $dp$ value at $i-(len[slink[x]]+diff[x])$ , where the previous endpoint is also $i-diff[x]$ . Use $g[x]$ to update $dp[i]$ , then repeat while following $slink[x]$ ; the new $dp$ contribution is included in each step.

The correctness relies on the following fact: if $x$ and $fail[x]$ belong to the same arithmetic-progression segment, 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]$ occurs at position $j$ in $(i-diff[x],i)$ . Since $x$ and $fail[x]$ are in the same arithmetic progression, $2|fail[x]| \ge x$ . The extra occurrence of $fail[x]$ overlaps the occurrence at $i-diff[x]$ ; call the overlap $w$ , and let $u$ satisfy $uw=fail[x]$ . As in Lemma $1$ , $w$ is a palindrome, and the prefix $s[i-len[x]+1..j]=uwu$ of $x$ is also a palindrome. This contradicts the fact that $fail[x]$ is the longest palindromic prefix (and suffix) of $x$ , whose previous occurrence is again $fail[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}$ . Count the valid partitions of $s$ .

Solution

Construct $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 becomes counting even-palindrome partitions of $t$ : change the transition above from a minimum to a sum and update $dp$ only at even positions. The time complexity is $O(n \log n)$ and the space complexity is $O(n)$ .

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

Palindromic Tree

Definition

Structure

Construction

Proof of the linear number of states

Theorem

Proof

Correctness proof

Applications

Number of distinct palindromic substrings

Number of occurrences of palindromic substrings

Minimum palindromic partition

Lemma 1

Lemma 2

Lemma 3

Lemma 4

Corollary

Optimization

Example problems

Further reading