Computing the maximum exponent in a stream

DOI10.1007/S00453-021-00883-YMaRDI QIDQ2118207zbMATH OpenOpenAlexFDO

Authors Oleg Merkurev, Arseny M. Shur

Publication date 22 March 2022

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-021-00883-y

zbMATH Keywords

streaming algorithmstringologyexponentgapped repeatperiodic string

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Algorithms in computer science (68Wxx) Combinatorics on words (68R15) Algorithms on strings (68W32) Graph theory (05Cxx)

Recommendations

• Computing maximal-exponent factors in an overlap-free word
• Maximal repetitions in strings
• Streaming periodicity with mismatches
• scientific article; zbMATH DE number 6691399
• Online detection of repetitions with backtracking

Cites work

• scientific article; zbMATH DE number 1390079 (Why is no real title available?)
• De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results
• Dynamic ordered sets with exponential search trees
• Efficient randomized pattern-matching algorithms
• Exact and Approximate Pattern Matching in the Streaming Model
• Fast Pattern Matching in Strings
• Growth of power-free languages over large alphabets
• Growth properties of power-free languages
• Near-optimal computation of runs over general alphabet via non-crossing LCE queries
• Optimal bounds for computing \({\alpha}\)-gapped repeats
• Real-time streaming string-matching
• Searching Long Repeats in Streams
• Searching of Gapped Repeats and Subrepetitions in a Word
• Surpassing the information theoretic bound with fusion trees
• Uniformly growing k-th power-free homomorphisms

Cited in

(4)

• Small-space algorithms for the online language distance problem for palindromes and squares
• Calculating Max and Min with exemplary sketch algorithm in data stream management system
• Searching runs in streams
• Computing maximal-exponent factors in an overlap-free word

This page was built for publication: Computing the maximum exponent in a stream

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