String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure
From MaRDI portal
Publication:5212816
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
Burrows-Wheeler transformpacked stringslongest common extension querieslongest common prefix queries
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
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
