• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

扩展KMP(Z函数)

开发技术 开发技术 2周前 (06-09) 11次浏览

给出两个字符串 (S)(T),长度分别为 (n)(m),要求求出两个数组 (A)(B)

(A)(T) 的每一个后缀与 (T) 的最长公共前缀长度,(B)(S) 的每一个后缀与 (T) 的最长公共前缀长度。

我们设我们有一个数组 (text{extend}),其中 (text{extend}[i]) 表示 (S[idots n])(T) 的最长公共前缀长度。

(text{extend}) 即为我们所求的 (B)

那么,我们如何来求这个 (text{extend}) 呢?先来看一组样例:

扩展KMP(Z函数)

我们求出 (text{extend}[1]) 之后,若暴力求 (text{extend}[2]),会差不多重新扫描一遍字符串。

当字符串的长度足够长时,时间开销会很大。所以我们要想办法避免重复扫描一些已经确定相等的字符串。

这里我们设另一个数组 (text{next}),其中 (text{next}[i]) 表示 (T[idots m])(T) 的最长公共前缀长度。也就是题目中所求 (A)

在上面这张图中,我们可以看到,(text{next}[2]=18),即 (T[1dots 18]=T[2dots 19])

又因为 (S[1dots 19]=T[1dots 19]),所以 (S[2dots 19]=T[2dots 19]),所以 (T[1dots 18]=S[2dots 19])

说明了什么?说明我们在求 (text{extend}[2]) 的时候,它的前 (18) 位都已经匹配成功了,直接从 (S[20])(T[19]) 开始匹配就可以了。

这也是 KMP 的思想,根据这个原理我们来研究扩展 KMP(Z 函数)。

先咕。


程序员灯塔
转载请注明原文链接:扩展KMP(Z函数)
喜欢 (0)