BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Finding Distinct Subpalindromes Online

preprint2013arXivOpen access
Dmitry KosolobovMikhail RubinchikArseny M. Shur
Data Structures and Algorithms
Read originalOpen PDFOpen graphSave paperReviewsDiscussion

Abstract

We exhibit an online algorithm finding all distinct palindromes inside a given string in time Θ(nlog⁡∣Σ∣)Θ(n\log|Σ|) over an ordered alphabet and in time Θ(n∣Σ∣)Θ(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.

Connections

Open full explorer

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite
Log in to review

No reviews yet.

Discussion 0

Add a commentWrite
Log in to comment

No comments yet.