On the sorting-complexity of suffix tree construction
From MaRDI portal
Publication:5487881
DOI10.1145/355541.355547zbMath1094.68694OpenAlexW2024147613WikidataQ56431599 ScholiaQ56431599MaRDI QIDQ5487881
No author found.
Publication date: 12 September 2006
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/355541.355547
Related Items
Efficient computation of sequence mappability ⋮ Minimal unique palindromic substrings after single-character substitution ⋮ Grammar index by induced suffix sorting ⋮ Self-indexed Text Compression Using Straight-Line Programs ⋮ Suffix-sorting via Shannon-Fano-Elias codes ⋮ Efficient computation of substring equivalence classes with suffix arrays ⋮ String Indexing with Compressed Patterns ⋮ Linear-time computation of DAWGs, symmetric indexing structures, and MAWs for integer alphabets ⋮ Generalizations of suffix arrays to multi-dimensional matrices. ⋮ A new efficient indexing algorithm for one-dimensional real scaled patterns ⋮ Linear-time construction of two-dimensional suffix trees ⋮ On demand string sorting over unbounded alphabets ⋮ Unnamed Item ⋮ On-line construction of parameterized suffix trees for large alphabets ⋮ Lightweight data indexing and compression in external memory ⋮ The indexing for one-dimensional proportionally-scaled strings ⋮ Efficient retrieval of approximate palindromes in a run-length encoded string ⋮ The parameterized suffix tray ⋮ PSIST: a scalable approach to indexing protein structures using suffix trees ⋮ The longest common substring problem ⋮ Computing Longest Single-arm-gapped Palindromes in a String ⋮ Computing longest palindromic substring after single-character or block-wise edits ⋮ Alphabet-independent linear-time construction of compressed suffix arrays using \(o(n \log n)\)-bit working space ⋮ Linear time algorithm for the longest common repeat problem ⋮ Practical Performance of Space Efficient Data Structures for Longest Common Extensions. ⋮ Algorithms for Indexing Highly Similar DNA Sequences ⋮ Full-Text Indexes for High-Throughput Sequencing ⋮ Substring Range Reporting ⋮ Substring range reporting ⋮ Faster approximate string matching for short patterns ⋮ Efficient construction of maximal and minimal representations of motifs of a string ⋮ On suffix extensions in suffix trees ⋮ Improving on-line construction of two-dimensional suffix trees for square matrices ⋮ Internal dictionary matching ⋮ Indexing weighted sequences: neat and efficient ⋮ Linearized suffix tree: An efficient index data structure with the capabilities of suffix trees and suffix arrays ⋮ Efficient computation of longest single-arm-gapped palindromes in a string ⋮ Efficient representation and counting of antipower factors in words ⋮ Finding Gapped Palindromes Online ⋮ Online algorithms for constructing linear-size suffix trie ⋮ Faster queries for longest substring palindrome after block edit ⋮ Quasi-Linear-Time Algorithm for Longest Common Circular Factor ⋮ Real two dimensional scaled matching ⋮ Efficient indexing algorithms for one-dimensional discretely-scaled strings ⋮ The suffix binary search tree and suffix AVL tree ⋮ Generalizations of suffix arrays to multi-dimensional matrices. ⋮ THE VIRTUAL SUFFIX TREE ⋮ Orthogonal Range Searching for Text Indexing ⋮ Sliding suffix tree ⋮ Constructing suffix arrays in linear time ⋮ ONLINE AND DYNAMIC RECOGNITION OF SQUAREFREE STRINGS ⋮ Inducing Suffix and LCP Arrays in External Memory ⋮ Suffix trays and suffix trists: structures for faster text indexing ⋮ Longest substring palindrome after edit
