Finding Distinct Subpalindromes Online

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.

7 pages

Cited by in corpus (3)

• The Number of Distinct Subpalindromes in Random Words
• Palindromic Trees for a Sliding Window and Its Applications
• Computing longest palindromic substring after single-character or block-wise edits