A pre-processing algorithm for string pattern matching

被引：0

作者：

Boxer, L ^{[1
]}

机构：

[1] Niagara Univ, Dept Comp & Informat Sci, Niagara Univ, NY 14109 USA

来源：

AMCS '05: Proceedings of the 2005 International Conference on Algorithmic Mathematics and Computer Science | 2005年

关键词：

string pattern matching; analysis of algorithms;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We introduce an algorithm that can be run in sublinear time and has, under certain circumstances, a high probability of greatly reducing the amount of data from the text that must be considered in order to solve string pattern matching problems.

引用

页码：29 / 32

页数：4

共 7 条

[1] [Anonymous], 1997, ALGORITHMS STRINGS T, DOI DOI 10.1017/CBO9780511574931
[2] THE BOYER-MOORE-GALIL STRING SEARCHING STRATEGIES REVISITED
APOSTOLICO, A
GIANCARLO, R
[J]. SIAM JOURNAL ON COMPUTING, 1986, 15 (01) : 98 - 105
[3] Coarse grained gather and scatter operations with applications
Boxer, L
Miller, R
[J]. JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2004, 64 (11) : 1297 - 1310
[4] FAST STRING SEARCHING ALGORITHM
BOYER, RS
MOORE, JS
[J]. COMMUNICATIONS OF THE ACM, 1977, 20 (10) : 762 - 772
[5] Knuth D. E., 1977, SIAM Journal on Computing, V6, P323, DOI 10.1137/0206024
[6] FAST STRING MATCHING WITH K-DIFFERENCES
LANDAU, GM
VISHKIN, U
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1988, 37 (01) : 63 - 78
[7] MILLER R, 2005, ALGORITHMS SEQUENTIA

← 1 →