Computing Palindromes on a Trie in Linear Time

A trie T is a rooted tree such that each edge is labeled by a single character from the alphabet, and the labels of out-going edges from the same node are mutually distinct. Given a trie T with n edges, we show how to compute all distinct palindromes and all maximal palindromes on T in O(n) time, in the case of integer alphabets of size polynomial in n. This improves the state-of-the-art O(n log h)-time algorithms by Funakoshi et al. [PSC 2019], where h is the height of T . Using our new algorithms, the eertree with suffix links for a given trie T can readily be obtained in O(n) time. Further, our trie-based O(n)-space data structure allows us to report all distinct palindromes and maximal palindromes in a query string represented in the trie T , in output optimal time. This is an improvement over an existing (naïve) solution that precomputes and stores all distinct palindromes and maximal palindromes for each and every string in the trie T separately, using a total O(n²) preprocessing time and space, and reports them in output optimal time upon query.