Computing palindromes on a trie in linear time
share
A trie π― 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 π― with n edges, we show how to compute all distinct palindromes and all maximal palindromes on π― 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. [PCS 2019], where h is the height of π―. Using our new algorithms, the eertree with suffix links for a given trie π― 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 π―, 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 π― separately, using a total O(n^2) preprocessing time and space, and reports them in output optimal time upon query.
READ FULL TEXT