KMP演示.ppt

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 注意:单引号是为字符串区别于变量名而设,它不是字符串的内容 称两个串是相等的 --- 当且仅当这两个串每个字符对应相等 串的模式匹配算法 1.求子串位置的定位函数 Index(S, T, pos) 采用定长顺序存储结构,不依赖其他串操作的匹配算法: 简单匹配算法的匹配过程示例 例如 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 = 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] 是: KMP算法的匹配过程示例 另一个模式串的例子是: 任选一主串举例如下: 第一趟a c a b a a b a a b c a c a a b c (i=1..2