扩展算法PPT讲稿.ppt

《扩展算法PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《扩展算法PPT讲稿.ppt（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、扩展算法扩展算法第1页，共17页，编辑于2022年，星期日【扩展的【扩展的KMPKMP算法】算法】扩展的扩展的KMPKMP问题：问题：给定母串S，和子串T。定义n=|S|,m=|T|，extendi=Si.n与T的最长公共前缀长度。请在线性的时间复杂度内，求出所有的extend1.n。第2页，共17页，编辑于2022年，星期日容易发现，如果有某个位置i满足extendi=m，那么T就肯定在S中出现过，并且进一步知道出现首位置是i而这正是经典的KMP问题。因此可见“扩展的KMP问题”是对经典KMP问题的一个扩充和加难。第3页，共17页，编辑于2022年，星期日例子 S=aaaaaaaaaabaa

2、a,T=aaaaaaaaaaa。第4页，共17页，编辑于2022年，星期日extend2=9。为了计算extend2，我们是不是也要进行10次比较运算呢？不然。因为通过计算extend1=10，我们可以得到这样的信息：S1.10=T1.10 S2.10=T2.10。计算extend2的时候，实际上是S2开始匹配T。因为S2.10=T2.10，所以在匹配的开头阶段是“以T2.10为母串，T为子串”的匹配。第5页，共17页，编辑于2022年，星期日设辅助函数nexti表示Ti.m与T的最长公共前缀长度。对上述例子，next2=10。也就是说：T2.11=T1.10 T2.10=T1.9 S2.10

3、=T1.9。这就是说前9位的比较是完全可以避免的！我们直接从S11T10开始比较。这时候一比较就发现失配，因此extend2=9。第6页，共17页，编辑于2022年，星期日下面提出一般的算法。设extend1.k已经算好，并且在以前的匹配过程中到达的最远位置是p。最远位置严格的说就是i+extendi-1的最大值，其中i=1,2,3,k；不妨设这个取最大值的i是a。(下图黄色表示已经求出来了extend的位置)第7页，共17页，编辑于2022年，星期日第一种情况第一种情况第8页，共17页，编辑于2022年，星期日第二种情况第二种情况第9页，共17页，编辑于2022年，星期日整个算法描述结束。上

4、述算法是线性线性算法。原因如下：容易看出，在计算的过程中，凡是访问过的点，都不需要重新访问了。一旦比较，都是比较以前从不曾探访过的点开始。因此总的时间复杂度是O(n+m),是线性的。第10页，共17页，编辑于2022年，星期日如何求解如何求解nextnext数组数组还剩下一个问题：next这个辅助数组怎么计算？复杂度是多少？我们发现计算next实际上以实际上以T为母串、为母串、T为子串的一个特殊为子串的一个特殊“扩展的扩展的KMP”。用上文介绍的完全相同的算法计算next即可。（用next本身计算next，具体可以参考标准KMP）此不赘述。第11页，共17页，编辑于2022年，星期日总结总结算

5、法的思想 已经访问过的点绝不再访问，充分利用已经访问过的点绝不再访问，充分利用已经得到的信息。已经得到的信息。第12页，共17页，编辑于2022年，星期日扩展扩展KMPKMP的一些应用的一些应用求解最长公共前缀长度求字符串中重复子串的长度 （利用next数组，nexti表示Ti.m与T的最长公 共前缀长度。找重复子串，比如abababccc，ababab就是重复子串；再比如 ababa，这个也是重复的，只是最后一个循环节不完整，端点处的循环节不完整的串也算作重复串。因此i+nexti的长度就是重复子串的长度。）例如poj2185第13页，共17页，编辑于2022年，星期日比如ababab，ne

6、xt2=4，2，3匹配0，1；然后4，5匹配2，3；相当于还是匹配0，1；所以0，1被重复了3次，所以只要是能匹配上的，就是在重复前i个字符，能匹配多长，就是重复了多长，直接用i+nexti就是最长的长度。第14页，共17页，编辑于2022年，星期日求解extend数组的模板void GetExtand(const EleType str,int strLen,int extand,const EleType mode,int modeLen,int next)int i,a,p,j(-1);for(i=0;i strLen;+i,-j)if(j=p)if(j 0)j=0,p=i;while(

7、p strLen&j modeLen&strp=modej)+p,+j;extandi=j,a=i;else extandi=nexti-a;第15页，共17页，编辑于2022年，星期日根据上面的模板，大家可以仿照写计算next的函数。poj2185主要求解next数组，唯一的不同在于此题是一个二维char数组，我们可以先把每一列看作一个点，这样整个二维数组看成一个字符串，算出nexti;在把每一行看作一个点，又一个字符串，再求出一组nexti。这两个过程中，分别对求出来的nexti,根据i+nexti=len（表示循环长度覆盖了整个串），进行判断筛选，将行与列的结果进行组合，即求得可行解。（题目要求的是面积）第16页，共17页，编辑于2022年，星期日Thank you！第17页，共17页，编辑于2022年，星期日