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

提出一种改进的字符串模式匹配算法。该算法对文本串进行预处理,即对文本串中不存在于模式串中的字符以及文本串中剩下的出现次数最少的字符分别进行标记,再通过匹配模式串的首尾字符来减少出现次数最少的字符的标记个数。发生匹配失败时,将模式串直接滑动到标记了的出现次数最少的字符处。通过实验证明,该算法的移动次数和比较次数有较大减少,耗费的额外空间的大小也不超过模式串的长度,进一步提高模式匹配的效率。

An Improved Character String Pattern Matching Algorithm

By analyzing a variety of improved pattern matching algorithms,an pattern matching algorithm is improved.Firstly,the text string is preprocessed.Two kinds of characters are made up.One does not exist in the pattern string,and the other is the characters that appear the least.Secondly,through matching both the first character and the last character of the pattern string,the number of the marked characters which appear the least is reduced.If the matching fails,the pattern string directly slides to the next marked character which appears the least.Finally,experimental results show that the frequencies of the movement and the comparison decreased greatly by the improved algorithm,and the additional cost of space is less than the length of the pattern string.Moreover,the efficiency of the pattern matching is improved.