2013/05/11 by Dmitry Kosolobov, Kosolobov, Dmitry, Mikhail Rubinchik +3
Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #cs.DS #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1305.2540
7 pages
arxiv created 2013/05/11 · openalex publication_date 2013/05/11 · arxiv updated 2013/05/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We exhibit an online algorithm finding all distinct palindromes inside a given string in time Θ(nlog|Σ|) 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.