Pattern matching with swaps

被引：23

作者：

Amir, A ^{[1
]}

Aumann, Y ^{[1
]}

Landau, GM ^{[1
]}

Lewenstein, M ^{[1
]}

Lewenstein, N ^{[1
]}

机构：

[1] Georgia Tech, Atlanta, GA USA

来源：

38TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 1997年

关键词：

D O I：

10.1109/SFCS.1997.646103

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 [计算机软件与理论];

摘要：

Let a text string T of n symbols and a pattern string P of m symbols from alphabet Sigma be given. A swapped version T' of T is a length n string derived from T by a series of local swaps, (i.e. t'(l) <-- t(l+1) and t'(l+1) <-- t(l)) where each element can participate in no more than one swap. The Pattern Matching with Swaps problem is that of finding all locations i for which there exists a swapped version T' of T where there is an exact matching of P in location i of T'. It has been an open problem whether swapped matching can be done in less than O(mn) time. In this paper we show the first algorithm that solves the pattern matching with swaps problem in time o(mn). We present an algorithm whose time complexity is O(nm(1/3) log m log(2) sigma) for a general alphabet Sigma, where sigma = min(m, \Sigma\).

引用

页码：144 / 153

页数：10