第七章符号串.ppt

《第七章符号串.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章字符串2021/9/81计算机算法设计与分析字符串的概念字符串是由零个或多个字符组成的有限序列集合，通常我们把字符串简称为串。在高级语言中一般都是用引号（“）或单引号（’）括起来，例如，串a1a2…an,，我们一般记为“a1a2…an,”或‘a1a2…an,’。2021/9/82计算机算法设计与分析串的几个概念1、长度：串s中字符的个数，记为length(s)。长度为0的串称为空串。2、子串：串中的连续字符序列。而包含子串的串称为主串。定义空串是任意串的子串。3、位置：字符的位置是它在串中的序号；子串的位置是它的首字符的位置。4、串

2、相等：两个串相等当且仅当它们完全一致，即长度和对应位置上的字符都相同。2021/9/83计算机算法设计与分析串的匹配给定长度为n的串T=t1t2……tn(T称为正文)，以及另一个串P=p1p2……pm(P称为模式)，查找模式P在正文T中首次出现或所有出现的位置的过程称为模式匹配。2021/9/84计算机算法设计与分析简单的串模式匹配算法将模式P看成关键字，从正文T的第1个元素开始，逐个与T中的P[0]个元素比较；如果这个长度为P[0]的子串与模式P相等，则匹配成功；否则，又从T的第2个元素开始进行同样的比较。如此继续T[0]–P[0]+1

3、步。2021/9/85计算机算法设计与分析简单的模式匹配算法intStrMatch(SStringS,SStringP)｛i=1；j=1；while(i<=S[0]&&j<=P[0])｛if(S[i]==P[j])｛i++;j++;｝else{i=i–j+2；j=1}｝if(j>P[0])returni–P[0]；return0;｝2021/9/86计算机算法设计与分析简单的模式匹配算法的评估在回朔深度不大的情况下，模式匹配算法的时间复杂度为O(m+n)在最坏情况下的时间复杂度为O(n*m)。2021/9/87计算机算法设

4、计与分析KMP算法KMP算法是D.Knuth与V.Pratt和J.Morris同时发现的，故称为Knuth_Morris_Pratt算法。其思想是：每当匹配过程中出现字符不等时，不是简单地从正文的下一个字符(即i+1)开始重新比较，而是利用已经得到的“部分匹配”的结果将模式串向右“滑动”尽可能远的一段距离后，再进行比较。KMP算法的时间复杂度为O(n+m)。2021/9/88计算机算法设计与分析能向右滑动多远？p1…pk…pj…pms1……si……sn当sipj，就将模式向右移动。假设pk和si相比较：s1……si……snp1…pk…p

5、j…pm显然应有：si–k+1…si–1=p1…pk–1。s…p1…而由前次的比较应有：si–k+1…si–1=pj–k+1…pj–1。于是得到这样的结果：p1…pk–1=pj–k+1…pj–1。2021/9/89计算机算法设计与分析滑动的距离只取决于模式模式滑动距离只取决于模式本身，与正文无关。设函数next[j]为当模式中第j个字符与正文中相应字符“失配”时，在模式中需重新和正文中该字符进行比较的字符的位置。0当j=1时next[j]=max{k

6、1

7、10计算机算法设计与分析一个模式的next(j)j：123456789模式：abaabaaabnext[j]：初始化：next[1]=0。0没有相应的k，next(j)为1。11k=2，下次从第二个元素开始比较。22依次以此类推可得其余元素的next(j)。34522021/9/811计算机算法设计与分析滑动不会造成遗漏KMP算法不再是将正文依次和模式中的元素逐个地进行匹配，而是当出现“失配”时从模式的第k(k=next(j))个元素开始重新比较，这样会不会遗漏掉可以匹配的子串呢？不会的。因为滑动的距离next(j)被定义为满足p1…pk

8、–1=pj–k+1…pj–1的最大的k。2021/9/812计算机算法设计与分析滑动不会造成遗漏引理7.1：正文S和模式P比较时，若si≠pj，则S没有以si–k0+1(next[j]1时，假设结论不成立，即存在这样的k0，那么有p1p2…pk0–1=si–k0+1si–k0+2…si–1。从而有，p1p2…pk0–1=pj–k0+1pj–k0+2…pj–1(7.3)由假设有next[j]

9、相矛盾；所以结论成立。2021/9/813计算机算法设计与分析KMP模式匹配算法intnext[MaxStrLen];//已算好的模式的next值intKMP_StrMatch(SString