Finding Distinct Subpalindromes Online
classification
💻 cs.DS
keywords
algorithmalphabetdistinctfindingonlinesigmathetatime
read the original abstract
We exhibit an online algorithm finding all distinct palindromes inside a given string in time $\Theta(n\log|\Sigma|)$ over an ordered alphabet and in time $\Theta(n|\Sigma|)$ over an unordered alphabet. Using a reduction from a dictionary-like data structure, we prove the optimality of this algorithm in the comparison-based computation model.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.