一种改进的BM字符串匹配算法

摘要

The essence of classical string matching algorithms is sequential character matching which is always from left to right or from right to left. In the main string, if there are many substrings which have the same prefix or suffix with the pattern string, the algorithms are in the low efficiency. The maximum length for the shift is the length of the pattern string. The improved algorithm uses the two-string-separate-comparison method, effectively avoiding meaningless comparison times due to the same prefix or suffix of substrings and the pattern string. Since the algorithm calculates moving distance of the pattern string according to the improved bad character rule, it increases moving distance of the pattern string. The experimental results show that the improved string matching algorithm can effectively reduce the string matching times and moving times to improve the algorithm efficiency.%经典字符串匹配算法的本质都是从左向右或者从右向左顺序进行字符匹配的，在主串中存在大量子串与模式串前缀或者后缀相同时效率较低，并且模式串最大右移长度为模式串长度。改进算法采用二分匹配字符串的方法，有效地避免了由主串中大量子串与模式串前缀相同或者后缀相同引起的无意义比较次数。模式串的移动距离根据改进的坏字符规则进行计算，增大了模式串的移动距离。实验结果表明，改进的字符串匹配算法可以有效地减少字符串的匹配次数和移动次数，达到了提高算法效率的目的。