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

摘要

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