A Linear-Time Algorithm for Seeds Computation
From MaRDI portal
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 (21)
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
This page was built for publication: A Linear-Time Algorithm for Seeds Computation
