IMPROVING THE WORST CASE RUNNING TIME OF THE BOYER-MOORE STRING MATCHING ALGORITHM

被引：69

作者：

GALIL, Z

机构：

[1] Tel-Aviv University, Tel-Aviv

来源：

COMMUNICATIONS OF THE ACM | 1979年 / 22卷 / 09期

关键词：

computational complexity; linear time; periodicity; string matching; worst case;

D O I：

10.1145/359146.359148

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

It is shown how to modify the Boyer-Moore string matching algorithm so that its worst case running time is linear even when multiple occurrences of the pattern are present in the text. © 1979, ACM. All rights reserved.

引用

页码：505 / 508

页数：4

共 7 条

[1] FAST STRING SEARCHING ALGORITHM [J].

BOYER, RS ;

MOORE, JS .

COMMUNICATIONS OF THE ACM, 1977, 20 (10) :762-772

[2]

Guibas L. J., 1977, 18th Annual Symposium on Foundations of Computer Science, P189, DOI 10.1109/SFCS.1977.3

[3]

Knuth D. E., 1977, SIAM Journal on Computing, V6, P323, DOI 10.1137/0206024

[4]

Lyndon R. C., 1962, MICH MATH J, V9, P289, DOI DOI 10.1307/MMJ/1028998773

[5] SPACE-ECONOMICAL SUFFIX TREE CONSTRUCTION ALGORITHM [J].

MCCREIGHT, EM .

JOURNAL OF THE ACM, 1976, 23 (02) :262-272

[6]

Weiner P., 1973, 14th Annual Symposium on Switching Automata Theory, P1

[7]

YAO ACC, 1977, THESIS STANFORD U

← 1 →