文档介绍：KMP模式匹配算法探讨
摘要介绍了KMP算法并与朴素查找算法进行了比较，提 出了前缀函数的概念，并利用改进的前缀函数改进KMP算法，最后结 合KMP的改进算法给出了多次匹配的算法。
关键词串匹配，前缀函数，KMP算法
在计算机科学领域，串的模式匹配（以下简称为串匹配）算法一 直都是研究焦点之一。在拼写检查、语言翻译、数据压缩、搜索引擎、 网络入侵检测、计算机病毒特征码匹配以及DNA序列匹配等应用中， 都需要进行串匹配。串匹配就是在主串中查找模式串的一个或所有出 现。在本文中主串表示为S=sls2s3・"sn,模式串表示为T=tlt2・"tm。 串匹配从方式上可分为精确匹配、模糊匹配、并行匹配等，著名的匹 配算法有BF算法、KMP算法、BM算法及一些改进算法。本文主要在精 确匹配方面对KMP算法进行了讨论并对它做一些改进以及利用改进的 KMP来实现多次模式匹配。
1 KMP算法
最简单的朴素串匹配算法（BF算法）是从主串的第一个字符和模 式串的第一个字符进行比较，若相等则继续逐个比较后续字符，否则 从主串的第二个字符起再重新和模式串的第一个字符进行比较。依次
类推，直至模式串和主串中的一个子串相等，此时称为匹配成功，否 则称为匹配失败。朴素模式匹配算法匹配失败重新比较时只能向前移 一个字符，若主串中存在和模式串只有部分匹配的多个子串，匹配指 针将多次回溯，而回溯次数越多算法的效率越低，它的时间复杂度一 般情况下为0((n-m+l)m)(注：n和m分别为主串和模式串的长度)， 最坏的情况下为O(m*n),最好的情况下为0(m+n)。KMP模式匹配算法 正是针对上述算法的不足做了实质性的改进。其基本思想是：当一趟 匹配过程中出现失配时，不需回溯主串，而是充分利用已经得到的部 分匹配所隐含的若干个字符，过滤掉那些多余的比较，将模式串向右 “滑动”尽可能远的一段距离后，继续进行比较，从而提高模式匹配 的效率，该算法的时间复杂度为O(m+n)。
那么如何确定哪些是多余的比较？在KMP算法中通过引入前缀 函数f(x)来确定每次匹配不需要比较的字符，保证了匹配始终向前进 行，无须回溯。假设主串为sls2, sn.,模式串为tlt2, tm.,其中m Mn,从si+1开始的子串遇到一个不完全的匹配，使得：
(1. 1)
如果我们能确定一个最小的整数，使得：
()
其中，所以确定i'等价于确定k,这里的k值就是我们要求的 前缀函数f(x)，只与给定的模 式串t中与主串匹配的q有关，即k=f(q),
f (q) =max(i | 0 i q 且 t[l. . i]是 的后缀｝ ()
确定KMP前缀函数的算法如下:
ftdefine MAXSIZE 100
Typedef unsigned char string[MAXSIZE+1] ;//0 号单元用来存
放串的长度
void f (sstring t, int *array)
{
m=t[0] ://m为当前模式串的长度
array= (int *)malloc ((m+1)*sizeof (int)) ;//0 号元不用
array[l]=0;k=0;
for(q=2:q<=m;q++)
{while(k>O&amp:&t[k+1]!=t[q])k=array[k]:
if(t[k+l]==t[q])k=k+l;
array[q]=k;
}
}
关于KMP算法的前缀函数f(x)的示例见表lo
表1模式串abaabcac
Ti
2
0
1
0
当模式串中有i个字符串匹配成功，第i+1个字符不匹配时，则 从i-f(i)个字符重新开始比较，这样不仅无须回溯，而且一次可以向 前滑动i-f(i)个字符，大大提高了模式匹配的效率。下面给出朴素匹 配算法和KMP匹配算法的比较，见表2o
表2朴素匹配算法和KMP匹配算法比较表
朴素算法
KMP算法
时间复杂度
0 ((n-m+l)m)
0 (m+n)
向前移动字符个数
1
q-f (q)
回溯次数
qT
无
其中：n为主串长度，m为模式串长度，q为匹配成功的字符个 数。 2 KMP算法的改进
在KMP算法的实际应用中，发现该算法也存在着不足，结合下面 的表一来论述KMP模式匹配算法的改进。假设模式串前4个字符与主 串的第i+l..i+4匹配成功，第5个字符匹配失败，此时前缀函数 f(4)二l