Linear-Time Construction of Suffix Arrays

DOI10.1007/3-540-44888-8_14zbMath1279.68068OpenAlexW1495956867MaRDI QIDQ3550835

Heejin Park, Dong Kyue Kim, Kun Soo Park, Jeong Seop Sim

Publication date: 6 April 2010

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-44888-8_14

Mathematics Subject Classification ID

Searching and sorting (68P10) Data structures (68P05) Algorithms on strings (68W32)

Related Items

Approximate string matching using compressed suffix arrays, A metric index for approximate string matching, Construction of Aho Corasick automaton in linear time for integer alphabets, Computing suffix links for suffix trees and arrays, Replacing suffix trees with enhanced suffix arrays, Locating maximal approximate runs in a string, A Probabilistic Analysis of the Reduction Ratio in the Suffix-Array IS-Algorithm, Lightweight algorithms for constructing and inverting the BWT of string collections, Optimal in-place suffix sorting, Efficient algorithms for three variants of the LPF table, Parallel suffix sorting for large string analytics, On demand string sorting over unbounded alphabets, The “Runs” Theorem, Period recovery of strings over the Hamming and edit distances, On the combinatorics of suffix arrays, Text indexing with errors, Fast profile matching algorithms - A survey, Algorithms for Indexing Highly Similar DNA Sequences, Faster suffix sorting, The affix array data structure and its applications to RNA secondary structure analysis, Lightweight BWT Construction for Very Large String Collections, An elegant algorithm for the construction of suffix arrays, Computing regularities in strings: a survey, Computing the longest previous factor, A quick tour on suffix arrays and compressed suffix arrays, Linear time algorithms for generalizations of the longest common substring problem, A note on the Burrows-Wheeler transformation, Unnamed Item, Linearized suffix tree: An efficient index data structure with the capabilities of suffix trees and suffix arrays, Lossless filter for multiple repetitions with Hamming distance, Linear Time Suffix Array Construction Using D-Critical Substrings, Faster entropy-bounded compressed suffix trees, Space efficient linear time construction of suffix arrays