Efficient algorithms for shortest partial seeds in words

DOI10.1016/j.tcs.2016.11.035zbMath1387.68313OpenAlexW2559503166MaRDI QIDQ1698721

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

Publication date: 16 February 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://kclpure.kcl.ac.uk/portal/en/publications/efficient-algorithms-for-shortest-partial-seeds-in-words(16905461-339c-4486-b01e-341ae52f466a).html

zbMATH Keywords

quasiperiodicitycoversuffix treeseedalgorithms on strings

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Related Items

Property Suffix Array with Applications in Indexing Weighted Sequences, String Covering: A Survey, Subsequence covers of words, Experimental evaluation of algorithms for computing quasiperiods, Efficient Computation of 2-Covers of a String., Quasi-Periodicity in Streams, Approximate cover of strings, \(k\)-approximate quasiperiodicity under Hamming and edit distance

Cites Work

• Unnamed Item
• Unnamed Item
• Enhanced string covering
• Fast algorithm for partial covers in words
• Efficient detection of quasiperiodicities in strings
• Optimal superprimitivity testing for strings
• Repetitions in strings: algorithms and combinatorics
• A linear-time algorithm for a special case of disjoint set union
• An on-line string superprimitivity test
• An optimal algorithm to compute all the covers of a string
• Covering a string
• Fast Algorithms for Finding Nearest Common Ancestors
• Jewels of Stringology
• A Linear-Time Algorithm for Seeds Computation
• Efficient Algorithms for Shortest Partial Seeds in Words
• Algorithms on Strings
• Computing the cover array in linear time