String Synchronizing Sets: Sublinear-Time BWT Construction and Optimal LCE Data Structure

Dominik Kempa, Tomasz Kociumaka

Burrows-Wheeler transform (BWT) is an invertible text transformation that, given a text $T$ of length $n$, permutes its symbols according to the lexicographic order of suffixes of…