A Linear-Time Algorithm for Seeds Computation
From MaRDI portal
Publication:4987445
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
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
