Covering a string

DOI10.1007/BF01955677zbMath0858.68067OpenAlexW2121328026MaRDI QIDQ1924404

Costas S. Iliopoulos, D. W. G. Moore, Kun Soo Park

Publication date: 16 October 1996

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01955677

zbMATH Keywords

string algorithmscombinatorial algorithms on wordscovering of stringsperiodicity of strings

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Related Items (30)

Algorithms For Computing Approximate Repetitions In Musical Sequences ⋮ Speeding up the detection of evolutive tandem repeats ⋮ COVERS FROM TEMPLATES ⋮ On left and right seeds of a string ⋮ Two strings at Hamming distance 1 cannot be both quasiperiodic ⋮ Covering problems for partial words and for indeterminate strings ⋮ Efficient seed computation revisited ⋮ Can we recover the cover? ⋮ Generalizations of suffix arrays to multi-dimensional matrices. ⋮ Computing maximal-exponent factors in an overlap-free word ⋮ String Covering: A Survey ⋮ 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 ⋮ Computing regularities in strings: a survey ⋮ Shortest covers of all cyclic shifts of a string ⋮ Approximate periods of strings ⋮ Generalized approximate regularities in strings ⋮ Quasi-Periodicity in Streams ⋮ A Linear-Time Algorithm for Seeds Computation ⋮ Generalizations of suffix arrays to multi-dimensional matrices. ⋮ Approximate cover of strings ⋮ Quasiperiodicity and string covering ⋮ Repetitive perhaps, but certainly not boring ⋮ Testing string superprimitivity in parallel ⋮ Quasi-Periodicity Under Mismatch Errors ⋮ \(k\)-approximate quasiperiodicity under Hamming and edit distance

Cites Work

• Unnamed Item
• Unnamed Item
• Efficient detection of quasiperiodicities in strings
• Optimal superprimitivity testing for strings
• The smallest automaton recognizing the subwords of a text
• An optimal algorithm for computing the repetitions in a word
• Optimal off-line detection of repetitions in a string
• An on-line string superprimitivity test
• Transducers and repetitions
• Fast Pattern Matching in Strings

This page was built for publication: Covering a string