Linear Time Suffix Array Construction Using D-Critical Substrings

DOI10.1007/978-3-642-02441-2_6MaRDI QIDQ3637104zbMATH OpenOpenAlexFDO

Authors Ge Nong, Sen Zhang, W. H. Chan

Publication date 7 July 2009

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

Full work available at URL https://doi.org/10.1007/978-3-642-02441-2_6

Mathematics Subject Classification ID

Searching and sorting (68P10) Algorithms on strings (68W32)

Recommendations

• Linear work suffix array construction
• Space efficient linear time construction of suffix arrays
• Linear-time suffix sorting -- a new approach for suffix array construction
• Space efficient linear time construction of suffix arrays
• An elegant algorithm for the construction of suffix arrays

Cites work

• Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
• Engineering a lightweight suffix array construction algorithm
• scientific article; zbMATH DE number 432779 (Why is no real title available?)
• scientific article; zbMATH DE number 2038766 (Why is no real title available?)
• Linear-time construction of suffix arrays (extended abstract)
• Optimal Lightweight Construction of Suffix Arrays for Constant Alphabets
• Space efficient linear time construction of suffix arrays

Cited in

(13)

• Suffix-sorting via Shannon-Fano-Elias codes
• A survey of string orderings and their application to the Burrows-Wheeler transform
• Computing regularities in strings: a survey
• Computing the longest previous factor
• On the possible patterns of inputs for block sorting in the Burrows-Wheeler transformation
• Optimal in-place suffix sorting
• Lightweight BWT construction for very large string collections
• Lightweight algorithms for constructing and inverting the BWT of string collections
• Efficient algorithms for three variants of the LPF table
• LCP array construction in external memory
• On the optimisation of the GSACA suffix array construction algorithm
• The longest common extension problem revisited and applications to approximate string searching
• Searching 2D-strings for matching frames

This page was built for publication: Linear Time Suffix Array Construction Using D-Critical Substrings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3637104)