首页 > 代码库 > KMP的妙用(利用next数组寻找字符串的循环节)

KMP的妙用(利用next数组寻找字符串的循环节)

利用KMP的next数组的性质,我们可以找到next数组的循环节。

先说结论:

设字符串长n,则若其  i % ( i – next[n] ) == 0 ,则其有循环节(循环节数目大于1),其循环节数目为 i / ( i – next[n] )

这里的next数组存储的是匹配到i匹配不成立时,下一个要匹配的位置。即next数组记录的是下一次匹配的位置,而不是下一次匹配的偏移量,若是记录的偏移量,只需修改一下公式即可。

言归正传,我们先证明第一个结论,根据下图来进行说明:


技术分享

若结论中的关系成立(整除为4段),则会出现如上图所示情况,其中,A2+A3+A4段 == A1’+A2’+A3’段。

由于

A2+A3+A4段 == A1’+A2’+A3’段

所以:

A2==A1’       A3==A2’      A4==A3’

又因为:

A1’==A1      A2’==A2      A3’==A3

所以:

A2==A1       A3==A2       A4==A3

具有循环节,结论得证。

根据next数组的性质,我们也可以得知此循环节的长度是最小的:

next[n]可以理解为字符串前缀与后缀最大的相同串。所以剩下的A1即为长度最小的循环节。

第二个结论很容易就能得出。

KMP的妙用(利用next数组寻找字符串的循环节)