Space-Efficient Indexes for Uncertain Strings

Esteban Gabory, Chang Liu, Grigorios Loukides +2

Strings in the real world are often encoded with some level of uncertainty. In the character-level uncertainty model, an uncertain string $X$ of length $n$ on an alphabet $\Sigma$ is a…