Fast Lightweight Suffix Array Construction and Checking

DOI10.1007/3-540-44888-8_5zbMath1279.68065DBLPconf/cpm/BurkhardtK03OpenAlexW2169708967WikidataQ56485250 ScholiaQ56485250MaRDI QIDQ3550827

Stefan Burkhardt, Juha Kärkkäinen

Publication date: 6 April 2010

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

Full work available at URL: http://edoc.mpg.de/201869

Mathematics Subject Classification ID

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

Related Items (25)

Tight lower bounds for the longest common extension problem ⋮ Suffix-sorting via Shannon-Fano-Elias codes ⋮ Faster Lightweight Lempel-Ziv Parsing ⋮ Optimal in-place suffix sorting ⋮ Parallel suffix sorting for large string analytics ⋮ Near-optimal quantum algorithms for string problems ⋮ Computing runs on a general alphabet ⋮ On the possible patterns of inputs for block sorting in the Burrows-Wheeler transformation ⋮ Dynamic and internal longest common substring ⋮ Faster semi-external suffix sorting ⋮ Counting suffix arrays and strings ⋮ The complexity of minimum difference cover ⋮ Lightweight BWT and LCP Merging via the Gap Algorithm ⋮ Fast BWT in small space by blockwise suffix sorting ⋮ Faster suffix sorting ⋮ An elegant algorithm for the construction of suffix arrays ⋮ A quick tour on suffix arrays and compressed suffix arrays ⋮ Unnamed Item ⋮ Space efficient algorithms for the Burrows-Wheeler backtransformation ⋮ Linearized suffix tree: An efficient index data structure with the capabilities of suffix trees and suffix arrays ⋮ Longest common substring made fully dynamic ⋮ Small-space LCE data structure with constant-time queries ⋮ Constructing suffix arrays in linear time ⋮ Distributed suffix trees ⋮ Linear-Time Algorithm for Long LCF with k Mismatches

This page was built for publication: Fast Lightweight Suffix Array Construction and Checking