叶 煜

(成都农业科技职业学院电子信息分院,四川成都 611130)

0 引 言

模式匹配(Pattern Matching)问题是计算机相关领域中的一个基本问题,也是复杂性理论中研究得最广泛的问题之一,其在文字编辑处理、图像处理、文献检索、自然语言识别、入侵检测等领域有着广泛的应用.所谓模式匹配,是指给定一个长为n的文本串T[1,n]和长为m的模式串P[1,m],找出文本串T中与模式串P精确匹配的子串的起始位置.好的模式匹配算法能显著地提高模式匹配的效率,因此,研究并设计快速的模式匹配算法具有重要的理论价值和实际意义.

1 算法与分析

目前,模式匹配算法在进行搜索实践时,最有影响的算法是K MP算法[1]和BM算法[2].

1.1 K MP算法

K MP算法由Knuth等于1977年提出,其基本思想是:采用从左向右比较的方法,设计一个与模式串本身局部匹配信息构造的模式值数组next,当匹配过程中出现失配时,利用模式值,将模式串向右“滑动”尽可能远的一段距离,使文本串的指针在匹配过程中不用回溯,保证文本串中每个字符只进行一次比较,从而提高模式匹配的效率.K MP算法的时间复杂度为O(n).

1.2 BM算法

BM算法由Boyer等于1977年提出的,其基本思想是:采用从右向左比较的方法,它包含两个并行的规则,坏字符规则和好后缀规则,当出现不匹配字符时,通过查询预处理好的坏字符移动表与好后缀移动表,选择移动距离较大值向后移动模式串,再进行下一轮匹配尝试.BM算法预处理阶段时间复杂度为O(m+s),s为与模式串P和文本串T相……