有关字符串循环节的⼀些性质
我们最常⽤的求⼀个字符串循环的算法是kmp。
字符串长度为0结论：
设$len=n-nxt[n]$
(1) $nxt[n]=0$  不存在循环节
(2) $nxt[n]>0$ $\&\&$ $n\%len\neq0$ 存在循环节但是长度不整除
(3) $nxt[n]>0$ $\&\&$ $n\%len=0$ 存在整除循环节
⽽且更长的循环节⼀定是$len$的倍数。
证明1：若为(2)，那么不存在⼀个长度更长的循环节使其整除。
⼀个⼩性质：对于(2),(3)情况，则$\forall 1\leq l \leq r \leq n$，$S[l,r]$满⾜(2)，当$(r-l+1)\%len=0$时满⾜(3)。
考虑反证法，证明不存在整除循环节$len$，满⾜$\exists nxt[n]>n-len$。
(1)$len\%(n-nxt[n])=0$，显然⽭盾。
(2)$len\%(n-nxt[n])\neq 0$，设$x=n-nxt[n]$。
$S[1,len]$和$S[len+1,2*len]$之间产⽣$S[1,x]$的前后缀相等，设其长度为pre。
考虑证明$nxt[n]=n-x+pre$，只需证明$S[x-pre+1,2*x-pre]=S[1,x]$即可，也是⽤$S[1,len]$和$S[len +1,2*len]$交叉的证明。都推出了⽭盾就证完了。
证明2：若(1)，则所有整除循环节长度是$len$的倍数。
证明与证明1⾮常类似，都是以推出更长循环节为⽭盾的。
但有时我们并不满⾜于对于⼀个串$|S|$以$O(n^2)$的复杂度搞出所有⼦串的循环节。
设以$i$为左端点开始的⼦串不同最⼩循环节的个数为$g(i)$。
结论：$\sum_{i=1}^{n}g(i)$是$n*logn$级别的。
证明：我想证明$g(i)$是logn级别的，但是遇到了瓶颈啊。。。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。