文档介绍：KMP字符串匹配
串类型的定义
非数值处理的对象基本上是字符串数据
串(string)(或称字符串)----
由零个或多个字符组成的有限序列
记为: s = ‘a1a2...an’(n>=0)
ai(1<=i<=n)是字母,数字或其它字符
n称为串的长度,n=0的串称为空串(Null string)
子串----串中任意个连续字符组成的子序列
包含子串的串叫主串
子串在主串中的位置----
子串的第一个字符在主串中的序号
串的例子
例如:a,b,c,d 四个字符串为
a=‘BEI’, b=‘JING’
c=‘BEIJING’, d=‘BEI JING’
它们的长度分别为 3,4,7,8
a和b都是c和d的子串
a在c和d中的位置都是1
b在c中的位置是4,而b在d中的位置是5
注意:单引号是为字符串区别于变量名而设,它不是字符串的内容
称两个串是相等的---
当且仅当这两个串每个字符对应相等
串的模式匹配算法
Index(S, T, pos)
采用定长顺序存储结构,不依赖其他串操作的匹配算法:
int Index(SString S, SString T, int pos)
{ // T是非空串,也称为模式,1<=pos<=S的长度。
// 若主串S中存在和模式T相同的子串,则返回它在主串
// S中第pos个字符之后第一次出现的位置;否则返回0。
i = pos; j = 1;
while(i<=S[0] && j <= T[0]){
if(S[i] == T[j]) { ++i; ++j;} // 继续比较后续字符
else { i = i-j+2; j =1;} // 指针后退重新开始匹配
}
if(j > T[0]) return i-T[0]; // 匹配成功
else return 0; // 匹配不成功
}
简单匹配算法的匹配过程示例
例如 T=“abcac”; S=“ababcabcacbab”
第一趟匹配 a b a b c a b c a c b a b (i=3)
a b c (j=3)
第二趟匹配 a b a b c a b c a c b a b (i=2)
a (j=1)
第三趟匹配 a b a b c a b c a c b a b (i=7)
a b c a c (j=5)
第四趟匹配 a b a b c a b c a c b a b (i=4)
a (j=1)
第五趟匹配 a b a b c a b c a c b a b (i=5)
a (j=1)
第六趟匹配 a b a b c a b c a c b a b (i=11)
a b c a c (j=6) 成功!
简单匹配算法的复杂度分析
设n = StrLength(S);m = StrLength(T);
最好情况的复杂度为O(n+m),如
T = “STING”
S = “A STRING SEARCHING EXAMPLE CONSISTING OF SIMPLE TEXT”
最坏情况的复杂度为O(n*m),如
T = “00000001”
S = “00000000000000000000000000000000000000000000000001”
模式匹配的一种改进算法(KMP算法)
KMP算法的改进在于:
每一趟匹配过程中出现字符比较不等时,不需要回朔i指针
只要利用已经“部分匹配”结果,调整j指针,即将模式向右滑动尽可能远的一段距离,来个提高算法效率.
上例的KMP算法匹配过程示意如下
第一趟匹配 a b a b c a b c a c b a b (i=3)
a b c (j=3)
第二趟匹配 a b a b c a b c a c b a b (i=3 -> 7)
a b c a c (j=1 -> 5)
第三趟匹配 a b a b c a b c a c b a b (i=7 -> 11)
(a)b c a c (j=2 -> 6)
显然算法复杂度为O(n+m)
KMP算法的基本思想(一)
假设主串为S=“s1s2...sn”,模式串为T=“t1t2...tm”
我们要解决的问题是:当“失配”(sitj)时,模式串T”向右滑动”的可行距离有多远;或者说,下一步si应该与模式串中的哪个字符比较?
可以推断:答案将完全取决于模式串,而与主串无关
因此,可以预先为模式串设定一个数组next[j],当“失配”(sitj)时,i不变,j改为next[j]
前面例子的 next[j] 是:
j 1 2 3 4 5
模式串 a b c a c
next[j] 0 1 1 1 2
KMP算法的匹配过程示例
另一个模式串