Computing the cover array in linear time

DOI10.1007/S00453-001-0062-2MaRDI QIDQ5956835zbMATH OpenOpenAlexFDO

Authors Y. Li, W. F. Smyth

Publication date 23 October 2002

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL http://researchrepository.murdoch.edu.au/id/eprint/27858/

zbMATH Keywords

cover arrayquasiperiod

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05)

Recommendations

• scientific article; zbMATH DE number 1003283
• Efficient seeds computation revisited
• Computing covers using prefix tables
• An optimal algorithm to compute all the covers of a string
• Cover array string reconstruction

Cited in

(40)

• Efficient algorithms for shortest partial seeds in words
• Efficient seed computation revisited
• New complexity results for the \(k\)-covers problem
• Universal reconstruction of a string
• Linear time inference of strings from cover arrays using a binary alphabet (extended abstract)
• String Covering: A Survey
• Quasi-periodicity under mismatch errors
• Efficient Computation of 2-Covers of a String.
• The set of parameterized k-covers problem
• On left and right seeds of a string
• \(k\)-approximate quasiperiodicity under Hamming and edit distance
• Two strings at Hamming distance 1 cannot be both quasiperiodic
• Generalized approximate regularities in strings
• On approximate enhanced covers under Hamming distance
• Optimality of some algorithms to detect quasiperiodicities
• Approximate cover of strings
• ALGORITHMS FOR APPROXIMATE K-COVERING OF STRINGS
• Can we recover the cover?
• Verifying an enhanced cover array in linear time
• Computing regularities in strings: a survey
• Finding the cyclic covers of a string
• String covering with optimal covers
• Computing covers using prefix tables
• Computing palindromic factorizations and palindromic covers on-line
• Enhanced string covering
• Cover array string reconstruction
• Experimental evaluation of algorithms for computing quasiperiods
• Computing the \(\lambda \)-covers of a string
• Quasi-Periodicity in Streams
• An optimal algorithm to compute all the covers of a string
• Computing Covers Under Substring Consistent Equivalence Relations
• Shortest covers of all cyclic shifts of a string
• Fast algorithm for partial covers in words
• Efficient seeds computation revisited
• Identifying all abelian periods of a string in quadratic time and relevant problems
• Enhanced covers of regular and indeterminate strings using prefix tables
• Period recovery of strings over the Hamming and edit distances
• Inferring strings from cover arrays
• Crochemore's partitioning on weighted strings and applications
• Approximation and fixed parameter algorithms for the approximate cover problem

This page was built for publication: Computing the cover array in linear time

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