本文共 1551 字,大约阅读时间需要 5 分钟。
KMP算法
9.1.1 简单模式匹配
先举一个简单模式匹配的例子。给定字符串 , ,判断T是不是S的子串。用简单模式匹配来解决这个问题,过程如图9.1。
在简单模式匹配过程中,分别利用计数指针i和j指示主串S和模式串T中当前正待比较的位置。该匹配过程的基本思想是:
从主串的pos位置的字符起和模式的第一个字
符比较,若相等,则继续逐个比较后续字符;
否则从主串的下一个字符位置起重新和模式串
的字符比较。依次类推,直至模式串T中的每
个字符依次和主串S中的一个连续的字符序列
相等,则称匹配成功,即T是S的子串。否则,
匹配失败,即T不是S的子串。
简单模式匹配算法:
int issubstr(char S[], char T[])
{
int l1, l2, i = 0, j = 0;
l1 = strlen( S ); //主串S的长度
l2 = strlen( T ); //模式串s的长度
while(i < l1 && j < l2)
{
if(S[i] == T[j])
{ i++; j++;} //继续匹配后续字符
else
{ i = i - j + 1; j=0;} //指针后退重新
} //开始匹配
if(j >= l2)
return 1; //匹配成功,T是S的子串
else
return 0; //匹配失败
}
简单匹配算法过程易于理解,且在某些应用场合如文本编辑等,效率也较高。例如,在
检查模式串 是否存在与主串 时,此算法的时间复杂度是 ,其中n和m分别是主串和模式串的长度。然而,当模式串为 ,主串为 时,此算法的时间复杂度为 ,这也是最坏的情况。
9.1.2 KMP算法的原理
KMP算法是有Knuth、Morris和Pratt三人设计的线性时间字符串匹配算法。此算法可以在 的时间数量级上完成串的模式匹配操作。其改进在于:每当一趟匹配过程中出现比较的两个字符不等时,不需回溯i指针,而是利用已经匹配部分的性质,将模式串向右“滑动”尽可能远的一段距离后,再继续进行比较。
再看图9.1的匹配过程,进行改进后得到以下匹
配过程,如图9.2。第一趟匹配是在i=2,j=2时匹配
失败,这时i指针不回溯,从i=2,j=0继续匹配。第
二趟匹配是在i=6,j=4时匹配失败。这时仔细观察可
以发现,T(0)=S(5),所以可以从i=6,j=1继续匹配直
至匹配成功。
现在讨论一般情况。假设主串为 ,
模式串为 ,从上例的分析可知,为了
实现改进算法,需要解决下述问题:当匹配过程中产
生“失配”(即 )时,模式串“向右滑动”可
行的距离有多远,也就是说,当主串中第i个字符与
模式串中第j个字符匹配失败时,主串中第i个字符
与模式串中哪个字符再比较可使得出结果比较的次数
最少?
由上述问题可以知道,当在模式串某个位置匹配失败时,为使得匹配次数最少,接下来要匹配的位置是确定的,且只和模式串本身有关,记成 ,其中 为匹配失败处字符的下标。
定义 函数为:
;当j=0时
max{k|1<=k<j且 ;
0 ; 其他情况
例如:对于字符串 ,可以得到其 数组为:
得到 数组的程序实现:
void get_next()
{
int i = 0, j = -1;
next[0] = -1;
while(i < len)
{
if(j == -1 || str[i] == str[j])
{
i++;
j++;
next[i] = j;
}
else
j = next[j];
}
}
得到了 数组后,进行字符串匹配时,每次比较失配时指向主串的指针不动,指向模式串的指针移到 数组确定的位置,继续比较,直至模式串到达串尾匹配成功或指向主串的指针到达串尾匹配失败。
转载地址:http://xsali.baihongyu.com/