Finding Distinct Subpalindromes Online
Dmitry Kosolobov, Mikhail Rubinchik, Arseny M. Shur · arXiv (Cornell University) · 2013
We exhibit an online algorithm finding all distinct palindromes inside a given string in time $Θ(n\log|Σ|)$ over an ordered alphabet and in time $Θ(n|Σ|)$ 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.