算法2--栈和队列.ppt

《算法2--栈和队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、串的模式匹配算法本节主要内容1.简单（经典，朴素）的模式匹配算法2.KMP算法3.改进的KMP算法2串的模式匹配算法串的模式匹配操作是串处理系统中非常重要的操作。模式匹配：求子串在主串中位置的操作，即子串的定位操作:Index（S,T,POS）。Index(S,T,pos)//求子串T在主串S中的位置（序号）参数要求:串S和T存在，T是非空串，1≤pos≤StrLength(S)。操作结果:若主串S中存在和串T值相同的子串,则返回T在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。串的模式匹配操作主要是Index(S,T,po

2、s)操作如何实现？？？3串的模式匹配算法核心算法：将主串的第pos个字符和模式串的第1个字符比较，若相等，继续逐个比较后续字符；若不等，从主串的下一字符起，重新与模式的第一个字符比较。直到主串的一个连续子串字符序列与模式串相等，匹配成功，返回值为S中与T匹配的子串中第一个字符的序号。否则，匹配失败，返回值0。采用定长顺序结构为例介绍串的模式匹配算法1、经典BF模式匹配算法4串的模式匹配算法-经典BF算法S="bccabcaabb"主串T="bcaa"子串也叫模式串ijS[i]==T[j]：++i；++j12345678910S[i]<>T[j

3、]:i=i-j+2；j=1i指针回溯5串的模式匹配算法-经典BF算法intIndex(SStringS,SStringT,intpos){//返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0。//其中，T非空，1≤pos≤StrLength(S)。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])returni-T[0];elsereturn0;}//Ind

4、ex匹配成功，返回在主串的第一个字符的位置匹配失败，返回0i回溯到下一次要比较的字符位置，相当于子串相对主串向右移动一个位置6串的模式匹配算法-经典BF算法分析：BF匹配算法在最坏情况下的效率例：S="aaaaaaaaaaaaaab",T="aaab",pos=1主串长度n=15，模式串长度m=4最坏情况是：主串前面15-4个位置都部分匹配到子串的最后一位，即这11位比较了4次，最后4位也各比较了一次，还要加上4！比较字符的次数为：11*4+4=48次在最坏的情况下，需要比较字符的总次数为(n-m)*m+m次，算法的时间复杂度为Ο（m*n）7

5、串的模式匹配算法-KMP算法KMP算法的改进思想：每当一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”的结果将模式串向右“滑动”尽可能远的一段距离后，继续进行比较。8串的模式匹配算法-KMP算法示例：S="ababcabcacbab",T="abcac"第一趟：ababcabcacbabi=3j=3第二趟：ababcabcacbabi=3j=1i=7j=5abcabcac9串的模式匹配算法-KMP算法示例：S="ababcabcacbab",T="abcac"第三趟：ababcabcacbabi=7j=2(a)

6、bcaci=11j=6j>T[0],匹配成功在整个匹配过程中，i指针没有回溯，时间复杂度为Ο（m+n）。为什么i指针可以不回溯？？10串的模式匹配算法-KMP算法原理分析:设主串为S="S1S2…Sn",模式串为T="T1T2…Tm"当主串第i个字符和模式串中第j个字符失配时，主串中i指针不回溯，假设应与模式串的第k个字符再比较，我们可以分析前k-1个字符无需比较是求得k的关键。主串第i个字符与模式串的第j个字符失配了，即Si≠Tj，假设此时主串的第i个字符应和模式串的第k（k

7、+1…Si-j+kSi-j+k+1…Si-2Si-1SiSi+1…Tj≠Tj-1=======Tj-2Tk+1TkT1T2Tj-k+1得到部分匹配结果："Si-k+1Si-k+2...Si-1"="Tj-k+1Tj-k+2...Tj-1"?Tk-1Tk-2又得到满足的等式："Si-k+1Si-k+2...Si-1"="T1T2...Tk-1"可得："T1T2...Tk-1"="Tj-k+1Tj-k+2...Tj-1"11串的模式匹配算法-KMP算法根据模式串推得的规律："T1…Tk-1"="Tj-(k-1)…Tj-1"和已知的当前失配位置j，

8、可以归纳出计算新起点k的表达式。令next[j]=k，表示当模式串第j个字符与主串中相应字符“失配”时，应用模式串中第k个字符重新和主串中字符进行比较。定义：模式串