Title :
A Practical and Average Optimal String Matching Algorithm Based on Lecroq
Author :
Fan Hongbo ; Yao Nianmin ; Ma Haifeng
Author_Institution :
Coll. of Comput. Sci. & Technol., Harbin Eng. Univ., Harbin, China
Abstract :
The Lecroq algorithm is the best current solutions of single pattern string matching for binary text. In this paper, we simplify Lecroq and propose a more practical variant which is named S-Lecroq. We analysis the complexity of S-Lecroq and proof that S-Lecroq is optimal in average.
Keywords :
character recognition; text analysis; Lecroq algorithm; S-Lecroq; binary text; optimal string matching algorithm; single pattern string matching; Algorithm design and analysis; Bioinformatics; Complexity theory; Computer science; Educational institutions; Fingers; Pattern matching; Lecroq; complexity; design of algorithm; q-grams hash; sting matching;
Conference_Titel :
Internet Computing for Science and Engineering (ICICSE), 2010 Fifth International Conference on
Conference_Location :
Heilongjiang
Print_ISBN :
978-1-4244-9954-0
DOI :
10.1109/ICICSE.2010.41
