Fast algorithm for partial covers in words

DOI10.1007/s00453-014-9915-3zbMath1337.68307OpenAlexW2145381651WikidataQ59408430 ScholiaQ59408430MaRDI QIDQ493243

Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen

Publication date: 3 September 2015

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

quasiperiodicitysuffix treecover of a word

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Extracting powers and periods in a word from its runs structure
• Enhanced string covering
• Finding the upper envelope of n line segments in O(n log n) time
• Efficient detection of quasiperiodicities in strings
• Optimal superprimitivity testing for strings
• Repetitions in strings: algorithms and combinatorics
• An on-line string superprimitivity test
• How many squares can a string contain?
• An optimal algorithm to compute all the covers of a string
• Linear time algorithms for finding and representing all the tandem repeats in a string
• On-line construction of suffix trees
• Data structures and algorithms for the string statistics problem
• Covering a string
• Cross-Document Pattern Matching
• A Fast Merging Algorithm
• Jewels of Stringology
• A Linear-Time Algorithm for Seeds Computation
• Algorithms on Strings
• Computing the cover array in linear time