Fast Variants of the Backward-Oracle-Marching Algorithm

Author

Fan Hongbo ; Yao Nianmin ; Ma Haifeng

Author_Institution

Coll. of Comput. Sci. & Technol., Harbin Eng. Univ., Harbin, China

fYear

2009

fDate

21-22 Dec. 2009

Firstpage

56

Lastpage

59

Abstract

This study focuses on the faster exact single pattern string matching algorithms. In all solutions, two variants of BOM, EBOM and FBOM are very efficient. We improved them and presented two algorithms named Simplified-EBOM and Simplified-FBOM through removing the unnecessary branches and accomplishing the core calculation of the algorithm in a 1-dimensional array. The experimental results indicated that Simplified-EBOM is fast for short patterns and it is 12% faster than its basis algorithm on average.

Keywords

automata theory; string matching; 1-dimensional array; backward-oracle-marching algorithm; factor automata; simplified-EBOM; simplified-FBOM; single pattern string matching algorithms; Algorithm design and analysis; Automata; Basis algorithms; Bills of materials; Computer science; Doped fiber amplifiers; Educational institutions; Electronic mail; Internet; Pattern matching; design of algorithms; factor automaton; string matching;

fLanguage

English

Publisher

ieee

Conference_Titel

Internet Computing for Science and Engineering (ICICSE), 2009 Fourth International Conference on

Conference_Location

Harbin

Print_ISBN

978-1-4244-6754-9

Type

conf

DOI

10.1109/ICICSE.2009.53

Filename

5521633