String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure

DOI10.1145/3313276.3316368zbMath1433.68132arXiv1904.04228OpenAlexW2963299914MaRDI QIDQ5212816

Tomasz Kociumaka, Dominik Kempa

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

Burrows-Wheeler transformpacked stringslongest common extension querieslongest common prefix queries

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05) Algorithms on strings (68W32)

Related Items (8)

Internal shortest absent word queries in constant time and linear space ⋮ Practical Wavelet Tree Construction ⋮ Efficient construction of the BWT for repetitive text using string compression ⋮ Unnamed Item ⋮ Near-optimal quantum algorithms for string problems ⋮ Space-efficient construction of compressed suffix trees ⋮ Practical Performance of Space Efficient Data Structures for Longest Common Extensions. ⋮ Quasi-Linear-Time Algorithm for Longest Common Circular Factor

This page was built for publication: String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure