Hi everyone!

Quite recently, a problem named Palindromes in Deque was added to the Library Checker that asks you to execute the following:

1. Add a character $$$c$$$ to the beginning or the end of a string $$$s$$$;
2. Remove a character from the beginning or the end of $$$s$$$.

In-between the queries you also need to maintain the number of distinct palindromes, and the size of the largest prefix- and suffix-palindromes of the current string.

The problem on Library Checker uses the approach from Double-Ended Palindromic Trees article by, presumably, liouzhou_101. The paper is quite long though, so after briefly looking through introduction part to familiarize myself with their main concepts, I decided to do something a bit different than they did. In this blog, I will explain my approach.

Recap

First, let's briefly recall what an eertree is.

If we consider all palindromes in a string $$$S$$$, we can organize them in two trees (for odd and even lengths, collectively called eertree), such that for a palindrome $$$T$$$, its children are all palindromes of form $$$cTc$$$ for any character $$$c$$$ that occur in the string.

Besides root vertices, the eertree of $$$S$$$ only has at most $$$n$$$ vertices, where $$$n = |S|$$$. This is due to the fact that whenever we add a letter $$$c$$$ to $$$S$$$, all potentially new palindromes are suffixes of $$$Sc$$$. At the same time, if one palindrome is a suffix of another, it also occurs in it as a prefix, meaning that among all suffix-palindromes of $$$Sc$$$, only the largest one is potentially new, compared to the set of palindromes of $$$S$$$.

The eertree also maintains a suffix link for each vertex, such that the suffix link of a palindrome $$$T$$$ is the largest suffix-palindrome of $$$T$$$. To put up an example, let $$$T = abacaba$$$, then the suffix link of $$$T$$$ would be $$$\operatorname{link}(T) = aba$$$.

Palindromes on stack

Consider the problem MMCC '15 P3 — Momoka, in which there is an additional constraints that we only ever append or pop characters at the back of the string. This variant of the problem is solved fairly simple, as you may maintain the stack of maximal suffix-palindromes for each prefix, and then pop states from the stack as you remove characters.

You also have to add letters in non-amortized time, which is doable

• in $$$O(\Sigma)$$$ by keeping a separate suffix link $$$\operatorname{link}(T, c)$$$ for each character $$$c$$$;
• in $$$O(\log n)$$$ by using "quick links" or "series links" from original eertree paper;
• in $$$O(\log \Sigma)$$$ by maintaining $$$\operatorname{link}(T, c)$$$ as a "persistent array".

Using the first approach, we arrive at a fairly simple and short implementation:

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 42, sigma = 26;
int len[maxn], link[maxn][sigma], qlink[maxn];
int to[maxn][sigma];
int cnt[maxn];
char s[maxn];
int sz, last, n;
int64_t total;

vector<int> states;

void Init() {
    fill(link[0], link[0] + sigma, 1);
    len[1] = -1;
    s[n++] = -1;
    sz = 2;
}

long long Type(char letter) {
    states.push_back(last);
    char c = letter;
    s[n++] = c -= 'a';
    if(s[n - 1] != s[n - len[last] - 2])
        last = link[last][c];
    if(!to[last][c]) {
        int u = to[link[last][c]][c];
        memcpy(link[sz], link[u], sizeof(link[sz]));
        link[sz][s[n - len[u] - 1]] = u;
        len[sz] = len[last] + 2;
        cnt[sz] = 1 + cnt[u];
        to[last][c] = sz++;
    }
    last = to[last][c];
    return total += cnt[last];
}

void Backspace() {
    n--;
    total -= cnt[last];
    last = states.back();
    states.pop_back();
}

Now, how we can enhance this to maintain eertree on deque?

Palindromes on deque

Essentially, what we need is in one way or another be able to find the largest prefix-palindrome or the largest suffix-palindrome of a string after each operation. It may be tempting to try maintaining two stacks, one for suffix-palindromes of all prefixes, and another for prefix-palindromes of all suffixes. Unfortunately, largest prefix-palindromes of all suffixes may change a lot when we change the last character of the string. Conversely, largest suffix-palindromes of all prefixes may change a lot when we change the first character of the string.

When we maintained eertree on a stack, we additionally maintained a stack of certain states. It would be only natural to now maintain a single deque of states when we try to maintain eertree on a deque. But what kind of states do we need? If we think about maximal suffix- or prefix-palindrome, a natural way to rephrase the definition would be: a maximal palindrome that is not a prefix/suffix of another palindrome.

That being said, we can take one of the following two approaches:

• "surfaces", aka palindromic substrings that are neither a prefix, nor a suffix of another palindrome;
• "maximal palindromes", aka palindromes substrings that are not contained in any other palindromic substring.

If we consider these sets of palindromic strings, maximal prefix/suffix palindromes of the whole string will always be among them. While the paper on arxiv maintains the structure of surfaces, I felt like it's not the most natural approach, because they don't seem to form a natural deque structure. But maximal palindromes do! Indeed, no two maximal palindromes may share their center, thus we can maintain them in a deque, ordered by their center position. More importantly, only $$$O(1)$$$ of them change when we append or remove a letter on any side.

Maximal palindromes deque