Online detection of repetitions with backtracking

DOI10.1007/978-3-319-19929-0_25zbMATH Open1432.68591arXiv1412.4471OpenAlexW1772969887MaRDI QIDQ2942265FDOQ2942265

Authors: Dmitry Kosolobov 

Publication date: 20 August 2015

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

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.

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

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

zbMATH Keywords

online algorithmbacktrackingsquare-freerepetition-free

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

• Branching frequency and Markov entropy of repetition-free languages
• Computing the maximum exponent in a stream
• Finding the leftmost critical factorization on unordered alphabet
• Computing runs on a general alphabet
• Efficient representation and counting of antipower factors in words
• 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)