AbstractLet $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$.
SubjectsAlgorithms, Analysis of algorithms, Combinatorial problems, Computational molecular biology, Probabilistic method, Lovasz local lemma
RightsThis Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).