Fast exact string matching algorithms

被引：76

作者：

Lecroq, Thierry ^{[1
]}

机构：

[1] Univ Rouen, Fac Sci & Tech, LITIS, F-76821 Mont St Aignan, France

来源：

INFORMATION PROCESSING LETTERS | 2007年 / 102卷 / 06期

关键词：

string matching; hashing; design of algorithms;

D O I：

10.1016/j.ipl.2007.01.002

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

String matching is the problem of finding all the occurrences of a pattern in a text. We propose a very fast new family of string matching algorithms based on hashing q-grams. The new algorithms are the fastest on many cases, in particular, on small size alphabets. (c) 2007 Elsevier B.V. All rights reserved.

引用

页码：229 / 235

页数：7

共 13 条

[1]

Allauzen C, 1999, LECT NOTES COMPUT SC, V1725, P295

[2]

[Anonymous], 2002, FLEXIBLE PATTERN MAT

[3]

Cantone D, 2003, LECT NOTES COMPUT SC, V2647, P47

[4]

Charras C, 2004, HDB EXACT STRING MAT

[5]

CROCHEMORE M, UNPUB FAST IMPLEMENT

[6]

Fredriksson K, 2005, LECT NOTES COMPUT SC, V3772, P376

[7] FAST STRING SEARCHING [J].

HUME, A ;

SUNDAY, D .

SOFTWARE-PRACTICE & EXPERIENCE, 1991, 21 (11) :1221-1248

[8] EFFICIENT RANDOMIZED PATTERN-MATCHING ALGORITHMS [J].

KARP, RM ;

RABIN, MO .

IBM JOURNAL OF RESEARCH AND DEVELOPMENT, 1987, 31 (02) :249-260

[9]

Navarro G., 2000, ACM J EXP ALGORITHMI, V5, P4, DOI DOI 10.1145/351827.384246

[10] A FAST pattern matching algorithm [J].

Sheik, SS ;

Aggarwal, SK ;

Poddar, A ;

Balakrishnan, N ;

Sekar, K .

JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES, 2004, 44 (04) :1251-1256

← 1 2 →