Online detection of repetitions with backtracking

DOI10.1007/978-3-319-19929-0_25MaRDI QIDQ2942265zbMATH OpenOpenAlexFDO

Authors 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

online algorithmbacktrackingsquare-freerepetition-free

Mathematics Subject Classification ID

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

Abstract: In this paper we present two algorithms for the following problem: given a string and a rational $e>1$, detect in the online fashion the earliest occurrence of a repetition of exponent $gee$ in the string. 1. The first algorithm supports the backtrack operation removing the last letter of the input string. This solution runs in $O(nlogm)$ time and $O(m)$ space, where $m$ is the maximal length of a string generated during the execution of a given sequence of $n$ read and backtrack operations. 2. The second algorithm works in $O(nlogsigma)$ time and $O(n)$ space, where $n$ is the length of the input string and $sigma$ is the number of distinct letters. This algorithm is relatively simple and requires much less memory than the previously known solution with the same working time and space. a string generated during the execution of a given sequence of $n$ read and backtrack operations.

Recommendations

• Efficient on-line repetition detection
• Space efficient search for maximal repetitions
• scientific article; zbMATH DE number 2051171
• An O(n log n) algorithm for finding all repetitions in a string
• scientific article; zbMATH DE number 3976360

Cites work

• scientific article; zbMATH DE number 3913712 (Why is no real title available?)
• An Optimal $O(\log \log N)$-Time Parallel Algorithm for Detecting all Squares in a String
• Computing and Combinatorics
• Efficient on-line repetition detection
• Lempel-Ziv factorization may be harder than computing all runs
• Mathematical Foundations of Computer Science 2005
• Near real-time suffix tree construction via the fringe marked ancestor problem
• Simple real-time constant-space string matching
• Time-space-optimal string matching
• Transducers and repetitions

Cited in

(6)

• Finding the leftmost critical factorization on unordered alphabet
• Branching frequency and Markov entropy of repetition-free languages
• Computing the maximum exponent in a stream
• Computing runs on a general alphabet
• Efficient on-line repetition detection
• Detecting one-variable patterns

This page was built for publication: Online detection of repetitions with backtracking

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