Efficient detection of quasiperiodicities in strings

DOI10.1016/0304-3975(93)90159-QzbMath0804.68109MaRDI QIDQ688155

Andrzej Ehrenfeucht, Alberto Apostolico

Publication date: 28 November 1993

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

zbMATH Keywords

periods in stringsquasiperiods in stringssubstring

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45)

Related Items

An optimal algorithm to compute all the covers of a string, On left and right seeds of a string, Quasiperiodic and Lyndon episturmian words, Episturmian words: a survey, Quasiperiodic Sturmian words and morphisms, Covering problems for partial words and for indeterminate strings, Covering a string, Efficient seed computation revisited, Enhanced string covering, Can we recover the cover?, Minimal critical exponent of quasiperiodic words, Finding the cyclic covers of a string, Coverability and multi-scale coverability on infinite pictures, String Covering: A Survey, The set of parameterized \(k\)-covers problem, Period recovery of strings over the Hamming and edit distances, Efficient algorithms for shortest partial seeds in words, Experimental evaluation of algorithms for computing quasiperiods, Efficient Computation of 2-Covers of a String., Fast algorithm for partial covers in words, A work-time optimal algorithm for computing all string covers, Efficient Seeds Computation Revisited, ALGORITHMS FOR APPROXIMATE K-COVERING OF STRINGS, String covering with optimal covers, Computing regularities in strings: a survey, IDENTIFYING ALL ABELIAN PERIODS OF A STRING IN QUADRATIC TIME AND RELEVANT PROBLEMS, Collage of two-dimensional words, An on-line string superprimitivity test, Optimality of some algorithms to detect quasiperiodicities, Approximate periods of strings, Coverability in Two Dimensions, The subsequence composition of a string, On approximate enhanced covers under Hamming distance, Quasiperiods of biinfinite words, Quasi-Periodicity in Streams, A Linear-Time Algorithm for Seeds Computation, Approximate cover of strings, Quasiperiodicity and string covering, Normal forms of quasiperiodic strings, Repetitive perhaps, but certainly not boring, Testing string superprimitivity in parallel, Optimal superprimitivity testing for strings, Quasi-Periodicity Under Mismatch Errors, \(k\)-approximate quasiperiodicity under Hamming and edit distance

Cites Work

• The equation \(a_ M=b^ Nc^ P\) in a free group
• Structural properties of the string statistics problem
• An optimal algorithm for computing the repetitions in a word
• Optimal off-line detection of repetitions in a string
• Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays
• Optimal parallel detection of squares in strings
• On the computational power of pushdown automata
• Factorizing words over an ordered alphabet
• An O(n log n) algorithm for finding all repetitions in a string
• A Space-Economical Suffix Tree Construction Algorithm
• A representation for linear lists with movable fingers
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item