An optimal algorithm to compute all the covers of a string

DOI10.1016/0020-0190(94)00045-XzbMath0814.68094OpenAlexW2084345246MaRDI QIDQ1329417

V. Pereyra

Publication date: 1994

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)00045-x

zbMATH Keywords

covers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Related Items

On left and right seeds of a string, Computing covers using prefix tables, String covers of a tree, Enhanced string covering, Can we recover the cover?, A characterization of the squares in a Fibonacci string, String Covering: A Survey, The set of parameterized \(k\)-covers problem, Efficient algorithms for shortest partial seeds in words, Crochemore's partitioning on weighted strings and applications, Experimental evaluation of algorithms for computing quasiperiods, Efficient Computation of 2-Covers of a String., Fast algorithm for partial covers in words, ALGORITHMS FOR APPROXIMATE K-COVERING OF STRINGS, String covering with optimal covers, Computing regularities in strings: a survey, Shortest covers of all cyclic shifts of a string, Optimality of some algorithms to detect quasiperiodicities, On approximate enhanced covers under Hamming distance, Quasi-Periodicity in Streams, Approximate cover of strings, Normal forms of quasiperiodic strings, Repetitive perhaps, but certainly not boring, Quasi-Periodicity Under Mismatch Errors, \(k\)-approximate quasiperiodicity under Hamming and edit distance

Cites Work

• Efficient detection of quasiperiodicities in strings
• The equation \(a_ M=b^ Nc^ P\) in a free group
• Optimal superprimitivity testing for strings
• An optimal algorithm for computing the repetitions in a word
• An on-line string superprimitivity test
• A fast string searching algorithm
• Strongly qth Power–Free Strings
• Fast Pattern Matching in Strings
• Unnamed Item
• Unnamed Item
• Unnamed Item