Fast algorithm for partial covers in words

DOI10.1007/S00453-014-9915-3MaRDI QIDQ493243zbMATH OpenOpenAlexWikidataFDO

Authors Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń

Publication date 3 September 2015

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00453-014-9915-3

zbMATH Keywords

suffix treequasiperiodicitycover of a word

Mathematics Subject Classification ID

Data structures (68P05) Combinatorics on words (68R15) Algorithms on strings (68W32)

Recommendations

• Fast Algorithm for Partial Covers in Words
• Algorithmic combinatorics on partial words
• Efficient algorithms for shortest partial seeds in words
• Efficient Algorithms for Shortest Partial Seeds in Words
• ALGORITHMS FOR APPROXIMATE K-COVERING OF STRINGS
• A work-time optimal algorithm for computing all string covers

Cites work

• scientific article; zbMATH DE number 1615296 (Why is no real title available?)
• scientific article; zbMATH DE number 2086666 (Why is no real title available?)
• A Fast Merging Algorithm
• Algorithms on Strings
• An on-line string superprimitivity test
• An optimal algorithm to compute all the covers of a string
• Computing the cover array in linear time
• Covering a string
• Cross-document pattern matching
• Data structures and algorithms for the string statistics problem
• Efficient detection of quasiperiodicities in strings
• Enhanced string covering
• Extracting powers and periods in a word from its runs structure
• Finding the upper envelope of n line segments in O(n log n) time
• How many squares can a string contain?
• Jewels of Stringology
• Linear time algorithms for finding and representing all the tandem repeats in a string
• On-line construction of suffix trees
• Optimal superprimitivity testing for strings
• Repetitions in strings: algorithms and combinatorics

Cited in

(15)

• Efficient algorithms for shortest partial seeds in words
• String Covering: A Survey
• Efficient Computation of 2-Covers of a String.
• \(k\)-approximate quasiperiodicity under Hamming and edit distance
• On approximate enhanced covers under Hamming distance
• Approximate cover of strings
• Can we recover the cover?
• Finding the cyclic covers of a string
• String covering with optimal covers
• Experimental evaluation of algorithms for computing quasiperiods
• Subsequence covers of words
• Fast Algorithm for Partial Covers in Words
• Quasi-Periodicity in Streams
• Efficient Algorithms for Shortest Partial Seeds in Words
• Approximation and fixed parameter algorithms for the approximate cover problem

This page was built for publication: Fast algorithm for partial covers in words

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