文档介绍：KM P模式匹配算法探讨
在计算机科学领域，串的模式匹配(以下简称为串匹配)算法一直都是研究 焦点之一。在拼写检查、语言翻译、数据压缩、搜索引擎、网络入侵检测、计算 机病毒特征码匹配以及DNA序列匹配等应用中，都需要进行串匹配。串匹配就 是在主串中查找模式串的 或所有出现。在本文中主串表不为S=s1 s2s3"*sn, 模式串表示为 W1t2-tmo串匹配从方式上可分为精确匹配、模糊匹配、并行 匹配等，著名的匹配算法有BF算法、KMP算法、BM算法及一些改进算法。本 文主要在精确匹配方面对KMP算法进行了讨论并对它做一些改进以及利用改进 的KMP来实现多次模式匹配。
1 KMP算法
最简单的朴素串匹配算法(BF算法)是从主串的第一个字符和模式串的第一 个字符进行比较，若相等则继续逐个比较后续字符，否则从主串的第二个字符起 再重新和模式串的第一个字符进行比较。依次类推，直至模式串和主串中的一个 子串相等，此时称为匹配成功，否则称为匹配失败。朴素模式匹配算法匹配失败 重新比较时只能向前移一个字符，若主串中存在和模式串只有部分匹配的多个子 串，匹配指针将多次回溯，而回溯次数越多算法的效率越低，它的时间复杂度一 般情况下为0((n-m+1)m)(注：n和m分别为主串和模式串的长度)，最坏的 情况下为O(m*n),最好的情况下为O(m+n)。KMP模式匹配算法正是针对上 述算法的不足做了实质性的改进。其基本思想是：当一趟匹配过程中出现失配时, 不需回溯主串，而是充分利用已经得到的部分匹配所隐含的若干个字符，过滤掉 那些多余的比较，将模式串向右“滑动”尽可能远的一段距离后，继续进行比较, 从而提高模式匹配的效率，该算法的时间复杂度为O(m+n)。
那么如何确定哪些是多余的比较？在KMP算法中通过引入前缀函数f(x) 来确定每次匹配不需要比较的字符，保证了匹配始终向前进行，无须回溯。假设 主串为s1s2, sn.,模式串为t1t2, tm.,其中mMn,从si+1开始的子串遇到 一个不完全的匹配，使得：
如果我们能确定一个最小的整数
其中
f(q)=max{i| 0 i q 且 t[1..i]是 t[1 ..q]的后缀} ()
确定KMP前缀函数的算法如下：
#define MAXSIZE 100
lypedef 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[1]=0;k=0;
for(q=2;q<=m ;q++)
{while(k>0&&t[k+1]『 t[q])k=array[k];
if(t[k+1]==t[q])k=k+1;
array[q]=k;
}
关于KM P算法的前缀函数f(x)的示例见表1。
表1 模式串abaabcac
I
1
2
3
4
5
6
7
8
T
a
b
a
a
b
f(i)
0
0
1
1
2
0
1
0
当模式串中有i个字符串匹配成功，第