基本数据结构0904数据结构8串B

传智播客数据结构教程（8）,讲师：尹成QQ:77025077博客:,C/C+,算法+实战,传智播客,高薪就业,第2页,1.定义,与同线性表相同，仍为一对一关系。,定长顺序存储、堆分配存储、串的块链存储,只能以“串的整体”作为操作对象,关键是理解串的最小操作子集中的函数，其他操作可基于这些函数具体实现。,串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。,上节课内容回顾,第3页,基础知识：两等长串是否相等的比较方法,intIs_Equal(SStringS,SStringT)inti=1;j=1;/定义i，j分别指示两串当前比较字符位置，相当于“指针”while(iT0)return1;/匹配成功时jT0，即T串长度，返回1，匹配成功elsereturn0;/匹配失败时jT0,返回0/Is_Equal,第4页,IntIndex(SStringS,SStringT,intpos)inti=pos,j=1;while(iT0)returni-T0;/子串结束，说明匹配成功elsereturn0;/Index,BF算法的实现即Index（）操作的实现,相当于子串向右滑动一个字符位置,匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置。,此函数仅仅就是从第pos个位置开始比较而已!,第5页,最恶劣情况分析：例如：S=aaaaaaab;t=ab;n8，m2（1）主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位都比较了m次，（2）别忘了最后m位也各比较了一次，还要加上m！,BF匹配算法的最坏时间复杂度？,(n-m+1)*m,O(n-m+1)*m)O(n*m),第6页,设从si开始与t串匹配成功的概率为pi，在等概率情况下pi=1/(n-m+1)，因此最好情况下平均比较的次数是：,即最好情况下的时间复杂度是O(n+m)。,最好情况是：（1）主串前面n-m个位置比较时第一位就不等，即这n-m位都只比较了n-m次（2）同样最后m位也各比较了一次，还要加上m！总共比较次数：i1m(设T在S中出现位置是i）,S=ababcabcmbcac,T=mbcac,第7页,KMP算法（特点：速度快，主串指针不回溯）,4.3串的模式匹配算法,BF算法的实现方式：依次将主串中和T串等长的子串与T进行比较，故需要进行一个循环！最坏情况下的时间复杂度是O(n*m);最好情况下的时间复杂度是O(n+m)。BF算法的本质穷举，效率低！子串和主串的指针都需要回溯！,第8页,S=ababcabcacbab,T=abcac,S=ababcabcacbab,T=abcac,S=ababcabcacbab,T=abcac,Index_kmp的返回值应为i=6,aba,abc,问：能否利用已经部分匹配的结果而加快模式串的滑动速度？而且主串S的指针i不必回溯？答：能！这就是下面要将的KMP算法的思路，可提速到O(n+m)！,BF算法的本质穷举，效率低！可否提高效率？,第9页,KMP算法（特点：速度快）,KMP算法设计思想KMP算法的推导过程KMP算法的实现（关键技术:计算nextj）KMP算法的时间复杂度,第10页,KMP算法利用已经部分匹配的结果而加快模式串的滑动速度!,KMP算法设计思想：(参见教材116-117）,KMP算法可以比BF算法每次滑动距离大,第11页,KMP算法的推导过程：（见教材P118）,需要讨论两个问题：如何“记忆”部分匹配结果？如何由“记忆”结果计算出主串S第i个字符应该与模式T中哪个字符再比较？即确定模式T中的新比较起点k.,第12页,KMP算法的推导过程：（见教材P118）,抓住部分匹配结果的两个特征：,则S前i-1i-(k-1)位T的j-1j-(k-1)位Si-(k-1)Si-1Tj-(k-1)Tj-1,在S的i处和T的第j字符处失配,第13页,KMP算法的推导过程：（见教材P118）,抓住部分匹配结果的两个特征：,则T的k-11位S前i-1i-(k-1)位即T1Tk-1Si-(k-1)Si-1,设目前应与T的第k字符开始比较,第14页,KMP算法的推导过程：,T1Tk-1Si-(k-1)Si-1,Si-(k-1)Si-1Tj-(k-1)Tj-1,T1Tk-1=Tj-(k-1)Tj-1,第15页,KMP算法的推导过程：（见教材P118）,T1Tk-1=Tj-(k-1)Tj-1,注意：j为当前已知的失配位置，我们的目标是计算新起点k，仅剩一个未知数k，理论上已可解，且k仅与模式串T有关！,讨论：计算nextj有何意义？*一旦失配，应从模式串T中第nextj个字符开始与S的失配点i重新开始匹配!且S串指针i不必回溯。nextj怎么求？,演示程序,第16页,讨论：nextj有何物理意义？,nextjmaxk|1kj且T1Tk-1=Tj-(k-1)Tj-1,模式串从首位往右直到K-1位,模式串从j的前一位往左直到K-1位,T：abcac,第17页,nextj函数表征着模式串T中两段字符之间相匹配的最大子串的长度（除串本身外）。可见，模式中相似部分越多，则nextj函数越大，它既表示模式T字符之间的相关度越高，也表示j位置以前与主串部分匹配的字符数越多。即：nextj越大，模式串向右滑动得越远，与主串进行比较的次数越少，时间复杂度就越低。,想一想：如果主串和模式均为二进制码流，用KMP算法效果如何？,讨论：nextj有何物理意义？,第18页,根据模式串T的规律：T1Tk-1=Tj-(k-1)Tj-11kj，和已知的当前失配位置j，可以归纳出计算新起点k的表达式。令k=nextj，则,讨论：nextj怎么求？,第19页,怎样计算模式T所有可能的失配点j所对应的nextj？,例：模式串T：abaabcac可能失配位j：12345678新匹配位nextj:,0,1,1,2,2,3,1,2,讨论：,j=1时,nextj0；因为属于“j=1”;j=2时,nextj1；因为属于“其他情况”；,刚才已归纳：,j=3时,k=2，只需查看T1=T2；,j=4时,k=2，3，要查看T1=T3和T1T2=T2T3,j=5时,k=2，3，4，要查看T1=T4、T1T2=T3T4和T1T2T3=T2T3T4,以此类推，可得后续nextj值。,演示程序,1kj,第20页,练习nextj？,011122323,011211234,T1Tk-1=Tj-(k-1)Tj-1,1kj,第21页,next函数的改进算法,前面定义的next函数在某些情况下还是有缺陷例如：模式aaaab与主串aaabaaaab匹配情况：,S:aaabaaaab,T:aaaab,i:123456789,aaaab,aaaab,aaaab,aaaab,第22页,因此，在计算next函数时，如果出现Tj=Tnextj=Tk则nextj=nextk=nextnextj,此时效率不高的原因为：,当Tj=Tnextj时，则,如果Si!=Tj，则必然有Si!=Tnextj,因此，Ti没有必要继续与Tnextj进行比较，而应该直接和Tnextj的下一个字符Tnextnextj进行比较。,此例中TjTnextj，j1，2，3，4,第23页,在计算next函数时，如果出现Tj=Tnextj=Tk则nextj=nextk=nextnextj,next函数的改进算法nextvalj,第一步：先计算nextj；第二步：如果Tj=Tnextj，则修改nextj=nextk=nextnextj;-copy,Nextvalj:00004,第24页,练习nextvalj:,011122323,011211234,011021311,010210104,Tj=Tnextj,copynext,第25页,IntIndex(SStringS,SStringT,intpos)inti=pos,j=1;while(iT0)returni-T0;/子串结束，说明匹配成功elsereturn0;/Index,回顾：BF算法的实现即Index（）操作的实现,相当于子串向右滑动一个字符位置,匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置。,第26页,第一步，先把模式T所有可能的失配点j所对应的nextj计算出来；第二步：执行定位函数index_kmp（与BF算法模块非常相似）,KMP算法的实现即Index()操作的实现（见教材P119）,IntIndex_KMP(SStringS,SStringT,intpos)i=pos;j=1;while(iT0)returni-T0;/子串结束，说明匹配成功elsereturn0;/Index_KMP,第27页,KMP算法的时间复杂度,因为计算nextj的时间为O(m);且Index_KMP函数（没有回溯）的匹配时间为O(n);所以KMP算法的总时间耗费为：O(n+m)注意：由于BF算法在一般情况下的时间复杂度也是O(n+m)，所以至今仍被采用。,第28页,本章小结,1.定义,与同线性表相同，仍为一对一关系。,定长顺序存储、堆分配存储、串的块链存储,只能以“串的整体”作为操作对象,关键是理解串的最小操作子集中的函数，其他操作可基于这些函数具体实现。,串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。,第29页,KMP算法（特点：速度快，主串指针不回溯）算法复杂度：O(n+m)nextj和nextvalj的手工和程序计算办法,*串的模式匹配算法,BF算法的实现方式：依次将主串中和T串等长的子串与T进行比较，故需要进行一个循环！最坏情况下的时间复杂度是O(n*m);最好情况下的时间复杂度是O(n+m)。子串和主串的指针都需要回溯！,第30页,作业题,2.编写程序:要求任意输入一字符串，输出其中单词的个数。（一个或多个空白分隔单词）,1.已知主串s=ADBADABBAABADABBADADA,模式串t=ADABBADADA。写出模式串t的next和nextval函数值，并由此画出采用改进KMP算法匹配的过程。,第31页,下周第三次实验（同时提交前两次实验报告）,第三次实验内容：1.采用栈求解任意输入10进制数转r进制输出。2.利用循环队列求解舞伴第一个问题。（已知m、n，求第x个男生t首曲子和第几个女生跳舞？）要求，写出栈和队的基本操作，然后调用，而不能直接写个main解决问题，请大家提前准备好程序，未准备者不允许进实验室！,第32页,附录：计算机如何计算nextj,nextj+1=nextj+1;,第33页,Nextj=k;(隐含T1k-1=Tj-(k-1)j-1，即上图绿色段相等现在Tk=Tj则T1k=Tj-(k-1)j，即黄色段相等,所以nextj+1=k+1=nextj+1,k,j,第34页,现在j=6，Nextj=k=2;因为前面左右都一段“A”现又有Tk=Tj，即T6=T2=B对nextj+1而言，前面的左右匹配串长就在原来的基础上加了1个，即“AB”=“AB”所以nextj+1=nextj+1=2+1=3-递推法,例如：,第35页,B.第二种情况：TkTj,此时我们要求nextj+1,实际上就是要求j+1位置之前T串中左右边相等子串的最大长度，也就是上图中标示的黄色串的长度，该怎么求呢？,第36页,T,此时我们可以假设T串既是主串也是模式串，在T和T进行比较到位置j时，出现了TkTj，那么此时主串指针j不回溯的情况下，T应该挪到哪里和j对其进行下次比较呢？显然是nextk,因为在T第k个位置发生了失配现象啊,好了，既然T可以挪动到2所示位置继续比较，隐含着什么呢？T的最右边黄色段和T最左边绿色段相等，这个长度正是我们要找的j+1位置之前T串左右相等的最大匹配串长啊，所以nextj+1=nextk+1=nextnextj+1;,1,2,T,T,此处最难懂，大家慢慢体会,第37页,j123456789,例如：,此时j=7，我们已知next7=3=k,因为其前左右都有“AB”,next3=1,现在T7T3，也就是TkTj，j=7时出现了失配现象，根据kmp算法思想，j不动，T应该移动到使其nextk与第j个位置对齐，也就是next3=1,应该和j对齐，此时对于j+1位置而言，其前面存在“A”=“A”串，长度为next3,所以有nextj+1=next8=nextk+1=nextnextj+1=next3+1=2,j,k,j+1,第38页,0111223,2,例续：,nextj+1=next8=nextk+1=nextnextj+1=next3+1=2,第39页,if(Tk=Tj)nextj+1=nextj+1;elsenextj+1=nextk+1;/nextnextj+1;,综上所述，在已知next1j的情况下，我们可以采用递推法来求nextj+1,只需要分以下两种情况考虑：,实际上第二种情况在编程时还要改进，因为取nextk和j对齐比的时候，如果T的第Tnextk个字符和Tj不相等，还会继续出现失配，还需要继续去求next，直到求到Tnextx=Tj为止，nextj+1=nextx+1,所以程序设计的时候，需要循环求next！,第40页,问：对模式串p,已知next1j,如何简捷计算其nextj+1？,next1=0;if(pnextj=pj)next