Dynamic Suffix Array with Sub-linear update time and Poly-logarithmic Lookup Time

Amihood Amir, Itai Boneh

The Suffix Array $S{A}_S[1\dots n]$ of an $n$-length string $S$ is a lexicographically sorted array of the suffixes of $S$. The suffix array is one of the most well known and widely…