Double-ended eertree

Revision en1, by adamant, 2024-06-09 17:29:46

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.

Tags eertree, palindromes, palindromic tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English adamant 2024-06-10 17:30:40 4768 Tiny change: 'ast$, and maximal p' -> 'ast$, and remove maximal p' (published)
en2 English adamant 2024-06-10 16:25:26 5300 Tiny change: ' on deque? Essentiall' -> ' on deque?\n\n### Palindromes on deque\n\nEssentiall'
en1 English adamant 2024-06-09 17:29:46 519 Initial revision (saved to drafts)