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

Sarmad Abbasi, Anirvan Sengupta

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

Let Σ be a finite alphabet and x ∈ Σn. A string y ∈ Σ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 ∈ Σn and an integer m ≤ n outputs an integer k and y ∈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.

Original languageEnglish (US)
Pages (from-to)135-139
Number of pages5
JournalInformation Processing Letters
Volume62
Issue number3
DOIs
StatePublished - May 14 1997
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Keywords

  • Algorithms
  • Analysis of algorithms
  • Combinatorial problems
  • Computational molecular biology
  • Lovász local lemma
  • Probabilistic method

Fingerprint

Dive into the research topics of 'An O(n log n) algorithm for finding dissimilar strings'. Together they form a unique fingerprint.

Cite this