Linear-time String Indexing and Analysis in Small Space

DOI10.1145/3381417zbMath1485.68079arXiv1609.06378OpenAlexW3010768629MaRDI QIDQ4987434

Djamal Belazzougui, Fabio Cunial, Veli Mäkinen, Juha Kärkkäinen

Publication date: 3 May 2021

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1609.06378

zbMATH Keywords

Burrows-Wheeler transformsuffix arraysuffix treecompressed indexesstring kernelcompressed suffix treecompact data structurescompressed suffix arraymatching statisticsmaximal repeatminimal absent wordsuffix-link treebidirectional BWT indexmaximal exact matchmaximal unique matchmonotone minimal perfect hash functionpartial rank query

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Algorithms on strings (68W32)

Related Items (7)

Algorithms and complexity on indexing founder graphs ⋮ Unnamed Item ⋮ Elastic founder graphs improved and enhanced ⋮ Fast compressed self-indexes with deterministic linear-time construction ⋮ Unnamed Item ⋮ Range majorities and minorities in arrays ⋮ Parallel computation of the Burrows Wheeler transform in compact space

This page was built for publication: Linear-time String Indexing and Analysis in Small Space