Inducing enhanced suffix arrays for string collections

DOI10.1016/j.tcs.2017.03.039zbMath1408.68041OpenAlexW2604363154MaRDI QIDQ526901

Felipe A. Louza, Guilherme P. Telles, Simon Gog

Publication date: 15 May 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.03.039

zbMATH Keywords

data structuressuffix arrayLCP arraydocument arraystring collections

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Related Items (9)

An LMS-based grammar self-index with local consistency properties ⋮ Algorithms to compute the Burrows-Wheeler similarity distribution ⋮ Efficient construction of the BWT for repetitive text using string compression ⋮ Lightweight BWT and LCP Merging via the Gap Algorithm ⋮ Computing the multi-string BWT and LCP array in external memory ⋮ A simple algorithm for computing the document array ⋮ Unnamed Item ⋮ Detecting Mutations by eBWT ⋮ Prefix-Free Parsing for Building Big BWTs

Uses Software

• deBWT

Cites Work

• Unnamed Item
• Unnamed Item
• Optimal suffix sorting and LCP array construction for constant alphabets
• Lightweight algorithms for constructing and inverting the BWT of string collections
• Cross-document pattern matching
• Linear time algorithms for generalizations of the longest common substring problem
• Replacing suffix trees with enhanced suffix arrays
• New space/time tradeoffs for top-\(k\) document retrieval on sequences
• Constructing suffix arrays in linear time
• Space efficient linear time construction of suffix arrays
• Lightweight LCP construction for very large collections of strings
• An improved algorithm for the all-pairs suffix-prefix problem
• Suffix Arrays: A New Method for On-Line String Searches
• Linear work suffix array construction
• Permuted Longest-Common-Prefix Array
• Document Listing on Repetitive Collections
• External Memory Generalized Suffix and LCP Arrays Construction
• Spaces, Trees, and Colors
• Inducing the LCP-Array
• Engineering External Memory Induced Suffix Sorting
• Fast and Lightweight LCP-Array Construction Algorithms
• Inducing Suffix and LCP Arrays in External Memory
• Two Efficient Algorithms for Linear Time Suffix Array Construction
• Algorithm Theory - SWAT 2004
• Linear-time Suffix Sorting - A New Approach for Suffix Array Construction.

This page was built for publication: Inducing enhanced suffix arrays for string collections