Tight tradeoffs for real-time approximation of longest palindromes in streams

DOI10.1007/s00453-019-00591-8zbMath1429.68338OpenAlexW2948372199WikidataQ127752194 ScholiaQ127752194MaRDI QIDQ2319637

Przemysław Uznański, Oleg Merkurev, Arseny M. Shur, Paweł Gawrychowski

Publication date: 20 August 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-019-00591-8

zbMATH Keywords

lower boundreal-time algorithmpalindromestreaming

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27) Algorithms on strings (68W32)

Related Items

Shortest unique palindromic substring queries in semi-dynamic settings ⋮ Data structures for computing unique palindromes in static and non-static strings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parallel detection of all palindromes in a string
• Testing Generalised Freeness of Words
• Real-Time Streaming String-Matching
• Dictionary Matching in a Stream
• Periodicity in Streams
• Efficient randomized pattern-matching algorithms
• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• A Linear-Time On-Line Recognition Algorithm for ``Palstar
• Fast Pattern Matching in Strings
• The k-mismatch problem revisited
• The Number of Distinct Subpalindromes in Random Words
• Exact and Approximate Pattern Matching in the Streaming Model
• Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams.