An on-line string superprimitivity test

DOI10.1016/0020-0190(92)90111-8MaRDI QIDQ1209376zbMATH OpenOpenAlexFDO

Authors Dany Breslauer

Publication date 16 May 1993

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1016/0020-0190(92)90111-8

zbMATH Keywords

string matchingperiodon-line linear-time algorithmquasiperiodsuperprimitivity

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Algorithms on strings (68W32)

Recommendations

• Optimal superprimitivity testing for strings
• Testing string superprimitivity in parallel
• Publication:4503964
• Enhanced string covering
• An optimal algorithm to compute all the covers of a string

Cites work

• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• Efficient detection of quasiperiodicities in strings
• Fast Pattern Matching in Strings
• Optimal superprimitivity testing for strings

Cited in

(48)

• Efficient algorithms for shortest partial seeds in words
• Efficient seed computation revisited
• Universal reconstruction of a string
• Testing string superprimitivity in parallel
• A work-time optimal algorithm for computing all string covers
• 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?
• Normal forms of quasiperiodic strings
• Computing regularities in strings: a survey
• Finding the cyclic covers of a string
• Covering a string
• String covering with optimal covers
• An extension of the periodicity lemma to longer periods
• Repetitive perhaps, but certainly not boring
• Computing covers using prefix tables
• String covers of a tree
• Enhanced string covering
• Quasiperiodicity and string covering
• Experimental evaluation of algorithms for computing quasiperiods
• Computing the \(\lambda \)-covers of a string
• Subsequence covers of words
• Finding all periods and initial palindromes of a string in parallel
• Quasi-Periodicity in Streams
• An optimal algorithm to compute all the covers of a string
• 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
• Verifying and enumerating parameterized border arrays
• The ``runs theorem
• Linear-time computation of prefix table for weighted strings {\&} applications
• Computing runs on a trie
• Inferring strings from cover arrays
• Crochemore's partitioning on weighted strings and applications
• Approximation and fixed parameter algorithms for the approximate cover problem
• String covers of a tree revisited
• Approximate periods of strings

This page was built for publication: An on-line string superprimitivity test

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