Double-Ended Palindromic Trees in Linear Time

Qisheng Wang, Ming Yang, Xinrui Zhu

The palindromic tree (a.k.a. eertree) is a data structure that provides access to all palindromic substrings of a string. In this paper, we propose a dynamic version of eertree, ca…