A Linear-Time Algorithm for Seeds Computation

DOI10.1145/3386369zbMath1484.68347arXiv1107.2422OpenAlexW3022427021MaRDI QIDQ4987445

Tomasz Kociumaka, Tomasz Walen, Jakub Radoszewski, Wojciech Rytter, Marcin Kubica

Publication date: 3 May 2021

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1107.2422

zbMATH Keywords

quasiperiodicitysubword complexitysuffix treeseed of a word

Mathematics Subject Classification ID

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

Related Items

On left and right seeds of a string, Minimal unique palindromic substrings after single-character substitution, Covering problems for partial words and for indeterminate strings, Finding the cyclic covers of a string, String Covering: A Survey, Efficient algorithms for shortest partial seeds in words, Experimental evaluation of algorithms for computing quasiperiods, Efficient Computation of 2-Covers of a String., Fast algorithm for partial covers in words, Computing regularities in strings: a survey, Shortest covers of all cyclic shifts of a string, Internal dictionary matching, On approximate enhanced covers under Hamming distance, Longest property-preserved common factor: a new string-processing framework, Constructing antidictionaries of long texts in output-sensitive space, Efficient representation and counting of antipower factors in words, Quasi-Periodicity in Streams, Computing the Antiperiod(s) of a String, Quasi-Linear-Time Algorithm for Longest Common Circular Factor, Lazy Lempel-Ziv Factorization Algorithms, \(k\)-approximate quasiperiodicity under Hamming and edit distance

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient algorithms for three variants of the LPF table
• New complexity results for the \(k\)-covers problem
• Efficient detection of quasiperiodicities in strings
• Optimal superprimitivity testing for strings
• A linear-time algorithm for a special case of disjoint set union
• An on-line string superprimitivity test
• Repetitive perhaps, but certainly not boring
• Transducers and repetitions
• Detecting leftmost maximal periodicities
• Covering a string
• Computing longest previous non-overlapping factors
• Computing the \(\lambda \)-covers of a string
• The subtree max gap problem with application to parallel string covering
• Efficient Seeds Computation Revisited
• Fast Algorithms for Finding Nearest Common Ancestors
• A universal algorithm for sequential data compression
• Jewels of Stringology
• Computing the λ-Seeds of a String
• Algorithms on Strings
• Computing the cover array in linear time