A Practical and Average Optimal String Matching Algorithm Based on Lecroq
Hongbo Fan, Nianmin Yao, Haifeng Ma · 2010
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.