Searching Long Repeats in Streams

DOI10.4230/LIPICS.CPM.2019.31MaRDI QIDQ5088923zbMATH OpenOpenAlexFDO

Authors Oleg Merkurev, Arseny M. Shur

Publication date 18 July 2022

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2019/10502/pdf/LIPIcs-CPM-2019-31.pdf/

zbMATH Keywords

Karplongest repeated reversed substringlongest repeated substringRabin fingerprintstreaming algorithmsuffix tree

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• Tight tradeoffs for real-time approximation of longest palindromes in streams
• Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams.
• Searching runs in streams
• scientific article; zbMATH DE number 6691399
• Computing the maximum exponent in a stream

Cites work

• Approximate Hamming distance in a stream
• Dictionary matching in a stream
• Dynamic weighted ancestors
• Efficient randomized pattern-matching algorithms
• Exact and Approximate Pattern Matching in the Streaming Model
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Near real-time suffix tree construction via the fringe marked ancestor problem
• On-line construction of suffix trees
• Order-preserving indexing
• Parallel construction of a suffix tree with applications
• Real-Time Streaming Multi-Pattern Search for Constant Alphabet
• Real-time streaming string-matching
• Streaming for aibohphobes: longest palindrome with mismatches
• The \(k\)-mismatch problem revisited
• The streaming \(k\)-mismatch problem
• Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams.
• Towards optimal approximate streaming pattern matching by matching multiple patterns in multiple streams

Cited in

(3)

• Computing the maximum exponent in a stream
• Searching runs in streams
• Regular languages in the sliding window model

This page was built for publication: Searching Long Repeats in Streams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5088923)