FAST STRING-MATCHING WITH MISMATCHES

被引：14

作者：

BAEZAYATES, RA ^{[1
]}

GONNET, GH ^{[1
]}

机构：

[1] SWISS FED INST TECHNOL, CH-8092 ZURICH, SWITZERLAND

来源：

INFORMATION AND COMPUTATION | 1994年 / 108卷 / 02期

关键词：

D O I：

10.1006/inco.1994.1007

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We describe and analyze three simple and fast algorithms on the average for solving the problem of string matching with a bounded number of mismatches. These are the naive algorithm, an algorithm based on the Boyer-Moore approach, and ad hoc deterministic finite automata searching. We include simulation results that compare these algorithms to previous works. (C) 1994 Academic Press, Inc.

引用

页码：187 / 199

页数：13

共 15 条

[1] GENERALIZED STRING MATCHING
ABRAHAMSON, K
[J]. SIAM JOURNAL ON COMPUTING, 1987, 16 (06) : 1039 - 1051
[2] A NEW APPROACH TO TEXT SEARCHING
BAEZAYATES, R
GONNET, GH
[J]. COMMUNICATIONS OF THE ACM, 1992, 35 (10) : 74 - 82
[3] BAEZAYATES RA, 1989, LECT NOTES COMPUT SC, V382, P75
[4] IMPROVED STRING SEARCHING
BAEZAYATES, RA
[J]. SOFTWARE-PRACTICE & EXPERIENCE, 1989, 19 (03) : 257 - 271
[5] BAEZAYATES RA, 1989, CS8917 U WAT DEP COM
[6] BAEZAYATES RA, 1989, 12TH P ANN ACM SIG C, P168
[7] FAST STRING SEARCHING ALGORITHM
BOYER, RS
MOORE, JS
[J]. COMMUNICATIONS OF THE ACM, 1977, 20 (10) : 762 - 772
[8] DERIVATIVES OF REGULAR EXPRESSIONS
BRZOZOWSKI, JA
[J]. JOURNAL OF THE ACM, 1964, 11 (04) : 481 - &
[9] Galil Z., 1986, SIGACT News, V17, P52, DOI 10.1145/8307.8309
[10] GONNET GH, 1991, HDB ALGORITHMS DATA

← 1 2 →