Prague Stringology Conference 2013

Dmitry Kosolobov, Mikhail Rubinchik and Arseny M. Shur

Finding Distinct Subpalindromes Online

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.

Download article: Article in PostScript Article in PDF BibTeX Reference
 PostScript   PDF   BibTeX reference 
Download presentation: Presentation