An O(n log n) algorithm for finding dissimilar strings

✍ Scribed by Sarmad Abbasi; Anirvan Sengupta

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 411 KB
• Volume: 62
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(97)00057-4

✦ Synopsis

Let P be a finite alphabet and x E Z'. A string y E Zm 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 0( n log n) algorithm which on input x E 2? and an integer m < n outputs an integer k and y E .Zm 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. @ 1997 Elsevier Science B.V.