Dynamic Suffix Array with Polylogarithmic Queries and Updates

Dominik Kempa, Tomasz Kociumaka

The suffix array $SA[\mathrm{1..}n]$ of a text $T$ of length $n$ is a permutation of $\{1,\dots ,n\}$ describing the lexicographical ordering of suffixes of $T$, and it is considered to be…