Optimal superprimitivity testing for strings
From MaRDI portal
Publication:811134
DOI10.1016/0020-0190(91)90056-NzbMath0734.68071OpenAlexW2056819372MaRDI QIDQ811134
Costas S. Iliopoulos, Alberto Apostolico, Martin Farach
Publication date: 1991
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(91)90056-n
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Parallel algorithms in computer science (68W10)
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, Computing covers using prefix tables, String covers of a tree, Computing the \(\lambda \)-covers of a string, Quasiperiodic Sturmian words and morphisms, Two strings at Hamming distance 1 cannot be both quasiperiodic, Covering problems for partial words and for indeterminate strings, Covering a string, Efficient seed computation revisited, Enhanced string covering, Can we recover the cover?, Finding the cyclic covers of a string, String Covering: A Survey, The set of parameterized \(k\)-covers problem, Subsequence covers of words, Period recovery of strings over the Hamming and edit distances, 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, A work-time optimal algorithm for computing all string covers, ALGORITHMS FOR APPROXIMATE K-COVERING OF STRINGS, String covering with optimal covers, Computing regularities in strings: a survey, An on-line string superprimitivity test, An extension of the periodicity lemma to longer periods, New complexity results for the \(k\)-covers problem, Shortest covers of all cyclic shifts of a string, Optimality of some algorithms to detect quasiperiodicities, Approximate periods of strings, Generalized approximate regularities in strings, 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, Quasi-Periodicity Under Mismatch Errors, \(k\)-approximate quasiperiodicity under Hamming and edit distance
Cites Work
