AN O(N-LOG-N) ALGORITHM FOR FINDING DISSIMILAR STRINGS

Let Sigma be a finite alphabet and x is an element of Sigma(n) . A str ing y is an element of 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 p resent an O(n log n) algorithm which on input x is an element of Sigma (n) and an integer m less than or equal to n outputs an integer k and y is an element of Sigma(m) such that: (1) y is k-dissimilar to x. (2) There does not exist a string z of length m which is k - 1 dissimilar to x. (C) 1997 Elsevier Science B.V.