Online Detection of Repetitions with Backtracking

DOI10.1007/978-3-319-19929-0_25zbMath1432.68591arXiv1412.4471OpenAlexW1772969887MaRDI QIDQ2942265

Dmitry Kosolobov

Publication date: 20 August 2015

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.4471

zbMATH Keywords

square-freeonline algorithmbacktrackingrepetition-free

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Online algorithms; streaming algorithms (68W27) Algorithms on strings (68W32)

Related Items

Branching frequency and Markov entropy of repetition-free languages ⋮ Finding the leftmost critical factorization on unordered alphabet ⋮ Computing runs on a general alphabet ⋮ Detecting One-Variable Patterns ⋮ Efficient representation and counting of antipower factors in words

Cites Work

• Unnamed Item
• Efficient on-line repetition detection
• Transducers and repetitions
• Time-space-optimal string matching
• Near real-time suffix tree construction via the fringe marked ancestor problem
• Lempel-Ziv Factorization May Be Harder Than Computing All Runs
• Simple Real-Time Constant-Space String Matching
• Computing and Combinatorics
• Mathematical Foundations of Computer Science 2005
• An Optimal $O(\log \log N)$-Time Parallel Algorithm for Detecting all Squares in a String

This page was built for publication: Online Detection of Repetitions with Backtracking