TY - JOUR
TI - An O(n log n) algorithm for finding dissimilar strings
DO - https://doi.org/doi:10.7282/t3-befz-pn24
AU - Abbasi, Sarmad
AU - Sengupta, Anirvan
PY - 1996
AB - 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$.
KW - Algorithms
KW - Analysis of algorithms
KW - Combinatorial problems
KW - Computational molecular biology
KW - Probabilistic method
KW - Lovasz local lemma
LA - English
ER -