Computing covers using prefix tables

DOI10.1016/j.dam.2015.05.019zbMath1350.68297arXiv1412.3016OpenAlexW1600674239MaRDI QIDQ313747

W. F. Smyth, Ali Alatabbi, M. Sohel Rahman

Publication date: 12 September 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.3016

zbMATH Keywords

coversstringscover arrayindeterminate stringslinear-time algorithmprefix tables

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items

String covers of a tree, Covering problems for partial words and for indeterminate strings, Crochemore's partitioning on weighted strings and applications, Experimental evaluation of algorithms for computing quasiperiods, Efficient Computation of 2-Covers of a String., On approximate enhanced covers under Hamming distance, Quasi-Periodicity in Streams

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Enhanced string covering
• Indeterminate string inference algorithms
• Indeterminate strings, prefix arrays \& undirected graphs
• A new approach to the periodicity lemma on strings with holes
• Optimal superprimitivity testing for strings
• Fast pattern-matching on indeterminate strings
• An on-line string superprimitivity test
• An optimal algorithm to compute all the covers of a string
• Inferring an indeterminate string from a prefix graph
• Prefix Table Construction and Conversion
• Efficient Seeds Computation Revisited
• AN ADAPTIVE HYBRID PATTERN-MATCHING ALGORITHM ON INDETERMINATE STRINGS
• Generalized String Matching
• Algorithmic Combinatorics on Partial Words
• Computing the cover array in linear time