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

Sarmad Abbasi; Anirvan Sengupta

doi:10.1016/s0020-0190(97)00057-4

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

Sarmad Abbasi, Anirvan Sengupta

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

Let Σ be a finite alphabet and x ∈ Σⁿ. 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 ∈ Σⁿ 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 language	English (US)
Pages (from-to)	135-139
Number of pages	5
Journal	Information Processing Letters
Volume	62
Issue number	3
DOIs	https://doi.org/10.1016/s0020-0190(97)00057-4
State	Published - May 14 1997
Externally published	Yes

All Science Journal Classification (ASJC) codes

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

Access to Document

10.1016/s0020-0190(97)00057-4

Cite this

@article{13d80a79c94b47a584c459492767b742,

title = "An O(n log n) algorithm for finding dissimilar strings",

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.",

keywords = "Algorithms, Analysis of algorithms, Combinatorial problems, Computational molecular biology, Lov{\'a}sz local lemma, Probabilistic method",

author = "Sarmad Abbasi and Anirvan Sengupta",

year = "1997",

month = may,

day = "14",

doi = "10.1016/s0020-0190(97)00057-4",

language = "English (US)",

volume = "62",

pages = "135--139",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

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

AU - Abbasi, Sarmad

AU - Sengupta, Anirvan

PY - 1997/5/14

Y1 - 1997/5/14

N2 - 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.

AB - 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.

KW - Algorithms

KW - Analysis of algorithms

KW - Combinatorial problems

KW - Computational molecular biology

KW - Lovász local lemma

KW - Probabilistic method

UR - http://www.scopus.com/inward/record.url?scp=0013658676&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0013658676&partnerID=8YFLogxK

U2 - 10.1016/s0020-0190(97)00057-4

DO - 10.1016/s0020-0190(97)00057-4

M3 - Article

AN - SCOPUS:0013658676

SN - 0020-0190

VL - 62

SP - 135

EP - 139

JO - Information Processing Letters

JF - Information Processing Letters

IS - 3

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this