扩展KMP算法要点.ppt

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