String Sanitization Under Edit Distance: Improved and Generalized

Takuya Mieno, Solon P. Pissis, Leen Stougie +1

Let $W$ be a string of length $n$ over an alphabet $\Sigma$, $k$ be a positive integer, and $\mathcal{S}$ be a set of length-$k$ substrings of $W$. The ETFS problem asks us to construct…