Abstract
Let $Sigma$ be a finite alphabet and $x in Sigma^n$. A string $y in Sigma^m$ is said to be $k$-dissimilar to $x$, if no $k$ length substring of $x$ is equal to any $k$ length substring of $y$. We present an $O(n log n)$ algorithm which on input $x in Sigma^n$ and an integer $m leq n$ outputs an integer $k$ and $y in Sigma^m$ such that: - $y$ is $k$-dissimilar to $x$. - There does not exist a string $z$ of length $m$ which is $k-1$ dissimilar to $x$.