Faster algorithms for string matching with k mismatches

被引：95

作者：

Amir, A

Lewenstein, M ^{[1
]}

Porat, E

机构：

[1] Bar Ilan Univ, Dept Math & Comp Sci, IL-52900 Ramat Gan, Israel

[2] Georgia Inst Technol, Coll Comp, Atlanta, GA 30332 USA

来源：

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC | 2004年 / 50卷 / 02期

基金：

美国国家科学基金会;

关键词：

design and analysis of algorithms; combinatorial algorithms on words; approximate string matching; Hamming distance;

D O I：

10.1016/S0196-6774(03)00097-X

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The string matching with mismatches problem is that of finding the number of mismatches between a pattern P of length in and every length in substring of the text T. Currently, the fastest algorithms for this problem are the following. The Galil-Giancarlo algorithm finds all locations where the pattern has at most k errors (where k is part of the input) in time O (nk). The Abrahamson algorithm finds the number of mismatches at every location in time O (nrootm log m). We present an algorithm that is faster than both. Our algorithm finds all locations where the pattern has at most k errors in time O(nrootk log k). We also show an algorithm that solves the above problem in time O ((n + (nk(3))/m) log k). (C) 2003 Elsevier Inc. All rights reserved.

引用

页码：257 / 275

页数：19

共 28 条

[1] GENERALIZED STRING MATCHING [J].