摘要: Forward-SBNDM is a recently introduced variation of the BNDM algorithm for exact string matching. inspects 2-gram in text such that first character last one an alignment window pattern and second then outside window. We present generalization this idea by inspecting several lookahead characters beyond integrate it with SBNDMq, q-gram BNDM. As result, we get new variations SBNDMq. In addition, introduce greedy skip loop SBNDM2. tune up our algorithms reference 2-byte read. According to experiments, best are faster than winners recent comparisons English, DNA, binary data.
aalto.fi 
sci-hub.se 参考文章(23)
M. Oguzhan Külekci, Filter Based Fast Matching of Long Patterns by Using SIMD Instructions. prague stringology conference. pp. 118- 128 ,(2009)
Susana Ladra, Oscar Pedreira, Jose Duato, Nieves R. Brisaboa, Exploiting SIMD Instructions in Current Processors to Improve Classical String Algorithms Advances in Databases and Information Systems. pp. 254- 267 ,(2012) , 10.1007/978-3-642-33074-2_19
Branislav Ďurian, Jorma Tarhio, Hannu Peltola, Jan Holub, Tuning BNDM with > q -grams algorithm engineering and experimentation. pp. 29- 37 ,(2009)
Hannu Peltola, Jorma Tarhio, Alternative Algorithms for Bit-Parallel String Matching string processing and information retrieval. pp. 80- 93 ,(2003) , 10.1007/978-3-540-39984-1_7
Simone Faro, Thierry Lecroq, An Efficient Matching Algorithm for Encoded DNA Sequences and Binary Strings combinatorial pattern matching. pp. 106- 115 ,(2009) , 10.1007/978-3-642-02441-2_10
T. Takaoka, Zhu Rui Feng, On improving the average case of the Boyer-Moore string matching algorithm Journal of Information Processing. ,vol. 10, pp. 173- 177 ,(1988)
Thierry Lecroq, Simone Faro, The Exact String Matching Problem: a Comprehensive Experimental Evaluation arXiv: Data Structures and Algorithms. ,(2010)
Branislav Ďurian, Jan Holub, Hannu Peltola, Jorma Tarhio, Improving practical exact string matching Information Processing Letters. ,vol. 110, pp. 148- 152 ,(2010) , 10.1016/J.IPL.2009.11.010
Daniel M. Sunday, A very fast substring search algorithm Communications of the ACM. ,vol. 33, pp. 132- 142 ,(1990) , 10.1145/79173.79184
Andrew Hume, Daniel Sunday, Fast string searching Software - Practice and Experience. ,vol. 21, pp. 1221- 1248 ,(1991) , 10.1002/SPE.4380211105