A new string matching algorithm

被引：5

作者：

Ahmed, M ^{[1
]}

Kaykobad, M

Chowdhury, RA

机构：

[1] Bangladesh Univ Engn & Technol, Dept Comp Sci & Engn, Dhaka 1000, Bangladesh

[2] Univ Texas, Dept Comp Sci, Austin, TX 78712 USA

来源：

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS | 2003年 / 80卷 / 07期

关键词：

string matching; complexity; Boyer-Moore algorithm;

D O I：

10.1080/0020716031000087113

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper a new exact string-matching algorithm with sub-linear average case complexity has been presented. Unlike other sub-linear string-matching algorithms it never performs more than n text character comparisons while working on a text of length n . It requires only O (m +sigma) extra pre-processing time and space, where m is the length of the pattern and sigma is the size of the alphabet.

引用

页码：825 / 834

页数：10

共 13 条

[1] OPTIMAL CANONIZATION OF ALL SUBSTRINGS OF A STRING
APOSTOLICO, A
CROCHEMORE, M
[J]. INFORMATION AND COMPUTATION, 1991, 95 (01) : 76 - 95
[2] THE BOYER-MOORE-GALIL STRING SEARCHING STRATEGIES REVISITED
APOSTOLICO, A
GIANCARLO, R
[J]. SIAM JOURNAL ON COMPUTING, 1986, 15 (01) : 98 - 105
[3] FAST STRING SEARCHING ALGORITHM
BOYER, RS
MOORE, JS
[J]. COMMUNICATIONS OF THE ACM, 1977, 20 (10) : 762 - 772
[4] Colussi L., 1990, Proceedings. 31st Annual Symposium on Foundations of Computer Science (Cat. No.90CH2925-6), P135, DOI 10.1109/FSCS.1990.89532
[5] CORRECTNESS AND EFFICIENCY OF PATTERN-MATCHING ALGORITHMS
COLUSSI, L
[J]. INFORMATION AND COMPUTATION, 1991, 95 (02) : 225 - 251
[6] Tight bounds on the complexity of the Apostolico-Giancarlo algorithm
Crochemore, M
Lecroq, T
[J]. INFORMATION PROCESSING LETTERS, 1997, 63 (04) : 195 - 203
[7] SPEEDING-UP 2 STRING-MATCHING ALGORITHMS
CROCHEMORE, M
CZUMAJ, A
GASIENIEC, L
JAROMINEK, S
LECROQ, T
PLANDOWSKI, W
RYTTER, W
[J]. ALGORITHMICA, 1994, 12 (4-5) : 247 - 267
[8] ON THE EXACT COMPLEXITY OF STRING MATCHING - UPPER-BOUNDS
GALIL, Z
GIANCARLO, R
[J]. SIAM JOURNAL ON COMPUTING, 1992, 21 (03) : 407 - 437
[9] IMPROVING THE WORST CASE RUNNING TIME OF THE BOYER-MOORE STRING MATCHING ALGORITHM
GALIL, Z
[J]. COMMUNICATIONS OF THE ACM, 1979, 22 (09) : 505 - 508
[10] ON SIMON STRING SEARCHING ALGORITHM
HANCART, C
[J]. INFORMATION PROCESSING LETTERS, 1993, 47 (02) : 95 - 99

← 1 2 →