一种高效的模式串匹配算法  

An efficient pattern matching algorithm for string searching

作　　者：赵晓[1] 何立风 王鑫[1] 姚斌[1] 巢宇燕 王亚妮[1] ZHAO Xiao HE Li-feng WANG xin YAO Bin CHAO Yu-yan WANG Ya-ni(College of Electrical and Information Engineering, Shaanxi University of Science ＆Technology, Xi’an 710021,China Faculty of Environment, Information and Business, Nagoya Sangyo University, Aichi 488-8711, Japan)

机构地区：[1]陕西科技大学电气与信息工程学院,陕西西安710021 [2]日本名古屋产业大学环境商务信息学院

出　　处：《陕西科技大学学报（自然科学版）》2017年第1期183-187,共5页Journal of Shaanxi University of Science & Technology

基　　金：国家自然科学基金项目(61601271;61471227;61603234);陕西省科技厅科技计划项目(2016SF-444);陕西省教育厅自然科学专项科研计划项目(16JK1087)

摘　　要：基于BM算法和Horspool算法,提出了一种简单且高效的模式串匹配算法.将匹配成功部分的每个字符作用于坏字符移动策略以获得多个移动参考量,从这多个参考量中选择最大值作为模式串的当前移动量.模式串在每个不匹配位置的移动量可以仅根据模式串预先计算获得.实验结果表明,该算法在任意不匹配位置所给出的移动量均是当前模式串的最大移动量,提高了模式串匹配的效率.According to the analysis of the famous BM algorithm and the Horspool algorithm, we propose a simple and efficient pattern matching algorithm for string searching. When a mismatch happens,for shifting the pattern to the right,the shift amount in the Horspool al-gorithm is computed by using the rightmost character of the current text substring to the bad-character strategy. In comparison, the shift amount of our algorithm is the maximum one among all the shift amounts computed by using each of the already-matched characters. The maximum shift amount for each mismatch position of the pattern can be pre-computed by u-sing the pattern only. Experimental results demonstrated that our algorithm can obtain a lar-ger shift amount for a mismatch, and thus enhanced the efficiency of pattern matching for string searching.

关 键 词：模式匹配 字符串匹配 BM算法 HORSPOOL算法 

分 类 号：TP393.0[自动化与计算机技术—计算机应用技术]