Optimal off-line detection of repetitions in a string

DOI10.1016/0304-3975(83)90109-3zbMath0497.68052OpenAlexW2024145045WikidataQ64357145 ScholiaQ64357145MaRDI QIDQ1170893

Alberto Apostolico, Franco P. Preparata

Publication date: 1983

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(83)90109-3

zbMATH Keywords

algorithm leaf- tree repetitions in a given textstring on a finite alphabet

Mathematics Subject Classification ID

Artificial intelligence (68T99)

Related Items

Algorithms For Computing Approximate Repetitions In Musical Sequences, Structural properties of the string statistics problem, A linear time lower bound on McCreight and general updating algorithms for suffix trees, Improved linear systolic algorithms for substring statistics, Speeding up the detection of evolutive tandem repeats, A fast algorithm for finding the positions of all squares in a run-length encoded string, More results on overlapping squares, ASYMPTOTIC BEHAVIOUR OF THE MAXIMAL NUMBER OF SQUARES IN STANDARD STURMIAN WORDS, Detecting morphic images of a word: On the rank of a pattern, Parallel construction of a suffix tree with applications, An efficient algorithm for online square detection, Data structures and algorithms for the string statistics problem, Unnamed Item, Locating maximal approximate runs in a string, Covering a string, On updating suffix tree labels, Computing primitively-rooted squares and runs in partial words, Computing Primitively-Rooted Squares and Runs in Partial Words, A characterization of the squares in a Fibonacci string, Constructing Words with High Distinct Square Densities, Large-scale detection of repetitions, On shuffled-square-free words, The three squares lemma revisited, Most pseudo-copy languages are not context-free, Efficient string matching on packed texts, Un réseau linéaire pour la reconnaissance des mots sans carré, Bounds on Powers in Strings, Detecting the morphic images of a word : improving the general algorithm, Maximal repetitions in strings, WORD COMPLEXITY AND REPETITIONS IN WORDS, Efficient parallel algorithms to test square-freeness and factorize strings, New simple efficient algorithms computing powers and runs in strings, Periodicity and repetitions in parameterized strings, Optimal parallel detection of squares in strings, Efficient on-line repetition detection, Efficient detection of quasiperiodicities in strings, Computing regularities in strings: a survey, On the maximum number of cubic subwords in a word, String matching problems over free partially commutative monoids, Linear time algorithms for finding and representing all the tandem repeats in a string, New complexity results for the \(k\)-covers problem, Forty Years of Text Indexing, NUMBER OF OCCURRENCES OF POWERS IN STRINGS, Optimal parallel suffix tree construction, On suffix extensions in suffix trees, Optimal bounds for computing \({\alpha}\)-gapped repeats, Approximate periods of strings, Simple and flexible detection of contiguous repeats using a suffix tree, Generalized approximate regularities in strings, Optimal parallel algorithms for periods, palindromes and squares, Repetition Detection in a Dynamic String, Range LCP, Transducers and repetitions, Fibonacci arrays and their two-dimensional repetitions, Detecting leftmost maximal periodicities, Repetitions in strings: algorithms and combinatorics, Quasiperiodicity and string covering, Normal forms of quasiperiodic strings, Repetitive perhaps, but certainly not boring, Optimal discovery of repetitions in 2D, Squares and primitivity in partial words, ONLINE AND DYNAMIC RECOGNITION OF SQUAREFREE STRINGS, The smallest automaton recognizing the subwords of a text, Optimal Parallel Searching an Array for Certain Repetitions, Periodicity and Repetitions in Parameterized Strings, Repetitions detection on a linear array with reconfigurable pipelined bus system, Optimal superprimitivity testing for strings, Three overlapping squares: the general case characterized \& applications

Cites Work