扩展KMP算法.ppt

扩展的扩展的KMP算法算法刘雅刘雅琼 【扩展的扩展的KMPKMP算法算法】扩扩展的展的KMPKMP问题问题：给定母串S，和子串T。定义n=|S|,m=|T|，extendi=Si.n与T的最长公共前缀长度。请在线性的时间复杂度内，求出所有的extend1.n。容易发现，如果有某个位置i满足extendi=m，那么T就肯定在S中出现过，并且进一步知道出现首位置是i而这正是经典的KMP问题。因此可见“扩展的KMP问题”是对经典KMP问题的一个扩充和加难。例子 S=aaaaaaaaaabaaa,T=aaaaaaaaaaa。extend2=9。为了计算extend2，我们是不是也要进行10次比较运算呢？不然。因为通过计算extend1=10，我们可以得到这样的信息：S1.10=T1.10 S2.10=T2.10。计算extend2的时候，实际上是S2开始匹配T。因为S2.10=T2.10，所以在匹配的开头阶段是“以T2.10为母串，T为子串”的匹配。设辅助函数nexti表示Ti.m与T的最长公共前缀长度。对上述例子，next2=10。也就是说：T2.11=T1.10 T2.10=T1.9 S2.10=T1.9。这就是说前9位的比较是完全可以避免的！我们直接从S11T10开始比较。这时候一比较就发现失配，因此extend2=9。下面提出一般的算法。设extend1.k已经算好，并且在以前的匹配过程中到达的最远位置是p。最远位置严格的说就是i+extendi-1的最大值，其中i=1,2,3,k；不妨设这个取最大值的i是a。(下图黄色表示已经求出来了extend的位置)第一种情况第一种情况第二种情况第二种情况整个算法描述结束。上述算法是线性线性算法。原因如下：容易看出，在计算的过程中，凡是访问过的点，都不需要重新访问了。一旦比较，都是比较以前从不曾探访过的点开始。因此总的时间复杂度是O(n+m),是线性的。如何求解如何求解nextnext数组数组还剩下一个问题：next这个辅助数组怎么计算？复杂度是多少？我们发现计算next实际上以实际上以T为母串、为母串、T为子串的一个特殊为子串的一个特殊“扩展的扩展的KMP”。用上文介绍的完全相同的算法计算next即可。（用next本身计算next，具体可以参考标准KMP）此不赘述。总结总结算法的思想 已经访问过的点绝不再访问，充分利用已经访问过的点绝不再访问，充分利用已经得到的信息。已经得到的信息。扩展扩展KMPKMP的一些应用的一些应用求解最长公共前缀长度求字符串中重复子串的长度 （利用next数组，nexti表示Ti.m与T的最长公 共前缀长度。找重复子串，比如abababccc，ababab就是重复子串；再比如 ababa，这个也是重复的，只是最后一个循环节不完整，端点处的循环节不完整的串也算作重复串。因此i+nexti的长度就是重复子串的长度。）例如poj2185比如ababab，next2=4，2，3匹配0，1；然后4，5匹配2，3；相当于还是匹配0，1；所以0，1被重复了3次，所以只要是能匹配上的，就是在重复前i个字符，能匹配多长，就是重复了多长，直接用i+nexti就是最长的长度。求解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(p strLen&j modeLen&strp=modej)+p,+j;extandi=j,a=i;else extandi=nexti-a;根据上面的模板，大家可以仿照写计算next的函数。poj2185主要求解next数组，唯一的不同在于此题是一个二维char数组，我们可以先把每一列看作一个点，这样整个二维数组看成一个字符串，算出nexti;在把每一行看作一个点，又一个字符串，再求出一组nexti。这两个过程中，分别对求出来的nexti,根据i+nexti=len（表示循环长度覆盖了整个串），进行判断筛选，将行与列的结果进行组合，即求得可行解。（题目要求的是面积）Thank you！