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

被引：2

作者：

Abbasi, S ^{[1
]}

Sengupta, A ^{[1
]}

机构：

[1] AT&T BELL LABS,LUCENT TECHNOL,THEORY GRP,MURRAY HILL,NJ 07974

来源：

INFORMATION PROCESSING LETTERS | 1997年 / 62卷 / 03期

关键词：

algorithms; analysis of algorithms; combinatorial problems; computational molecular biology; probabilistic method; Lovasz local lemma;

D O I：

10.1016/S0020-0190(97)00057-4

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Let Sigma be a finite alphabet and x is an element of Sigma(n) . A string 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 present 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.

引用

页码：135 / 139

页数：5