如何利用KMP的next求字符串的循环节

2017-05-23 105点热度 0人点赞

利用KMP算法中的next值可以求出字符串的循环节,如ababab的循环节为ab,abcd的循环节为abcd,具体做法如下:假设字符串的长度为len,next[len]为字符串的最后一个字符的下一个字符的next值(下标从0开始),如果len % (len - next[len]) == 0,那么循环节的循环次数为len / (len - next[len]),否则为1,为什么呢?详细说明如下:

首先,对于给定的长度为len的字符串str,根据next的定义可知,str[0~(next[j]-1)] = str[(j-next[j])~(j-1)],且next[j]为满足该条件的值当中的最大那一个,令循环次数为k,则

当k = 1时,根据next的意义可知next[len] = 0,所以len / (len - next[len]) = 1,结论正确;

当k = 2时,如abcdabcd,如果最后一个d后面还有字符的话,那么它的next的值应该指向第二个a,为4,len % (len - next[len])= 8 % (8 - 4) = 0,循环次数为2,结论正确;

当k >= 3时,有len = k * (len - next[len])(x >= 3),next[len] = (1 - 1 / k) * len > (1 / 2) len,即next[len]位于字符串的中间位置之后,如图1所示,且黄色部分与蓝色部分一样,

如何利用KMP的next求字符串的循环节   图1

 

所以,在图2中,紫色部分跟绿色部分也一样(假设二者长度一样),

如何利用KMP的next求字符串的循环节   图2

 

由于黄色部分跟蓝色部分是一样,且蓝色部分结尾的两段(紫色跟绿色)是一样的,因而黄色部分在结尾部分也应该有两段一样的,即绿色跟它前面相同长度的一段,假设为红色,此时红色部分是蓝色部分的倒数第三段,且跟前两段一样,这也将导致黄色部分也将产生倒数第三段,这样,蓝色部分的倒数第k段永远是是黄色部分的倒数第k-1段,只要证明蓝色跟黄色的公共部分是紫色部分的整数倍,那么就可以说该公共部分是由n个紫色部分组成,由于蓝色部分跟黄色部分长度一样,二者又有公共部分,所以图2中红色部分跟紫色部分长度一样,又因为整个字符串长度是紫色部分的整数倍(>=
3),所以公共部分的长度也是紫色部分的整数倍(>= 1),如此一来,公共部分部分是由n个紫色部分组成(n >= 1),从而红色部分跟紫色部分也必然一样(红色部分是黄色部分的跟紫色长度相同的第一部分),所以,整个字符串是由n个紫色部分组成的(n >= 3),结论正确。

综上所述,结论的充分性得证,另外,由next的意义可以很容易证明必要性。

未经允许不得转载!如何利用KMP的next求字符串的循环节

本文地址:https://ai.52learn.online/563

站长邮箱:ai52learn@foxmail.com