KMP算法求串的循环节长度
next数组
next
数组的作用: 在失配时, 应该将模板串的指针指向哪个位置
next
数组的意义: 前面长度为i的字串中, 前后缀相等的最大长度
求法一
1 | memset(next, 0, sizeof next); |
求法二
1 | memset(next, 0, sizeof next); |
两种写法的思想都是差不多的, 要利用已经求好的数组加速向前跳
求循环节
最后next[n]
表示的就是整个字符串前后缀相等的长度
显然, 对于某个字符串T
,长度为n
,由长度为l
的字符串s
重复k
次得到,当k >= 2
时必然有T.substr(0, n - l - 1) == T.substr(l, n - l - 1)
. 由于next
表示的是前后缀的最长长度, 因此在已知T
是循环串的情况下, 一个循环节的长度就是n - next[n]
.
若T
不是一个完美的循环串, 其最后一个循环节缺失了一部分, 以上写法依然可以得到正确的循环节长度, T
再补上l - n % l
的长度就是循环串了

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License
Permalink: https://duanyll.com/2019/07/15/KMP-Loop/