Title :
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
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;
Conference_Titel :
Internet Computing for Science and Engineering (ICICSE), 2009 Fourth International Conference on
Conference_Location :
Harbin
Print_ISBN :
978-1-4244-6754-9
DOI :
10.1109/ICICSE.2009.53
