-
border 理论
-
一些定义
- fail(s) 为 \(s\) 的最长的非满前缀=后缀的长度
- border(s) 为 \(s\) 的所有满足前缀=后缀（非满）的长度集合
- 若长度为 \(n\) 的字符串存在 \(a\) 的周期，且 \(a | n\) 那么 \(a\) 是 \(n\) 的满周期
- 若存在长度为 \(k\) border，则有 \(n-k\) 的周期
-
弱周期引理
若 \(s\) 存在长度为 \(a,b\) 的周期，若 \(a+b<=n\) 则存在 \(\gcd(a,b)\) 的周期
证明：
- \(\forall i \in [1,n-a],s_i = s_{i+a}\), \(\forall i\in[1,n-b],s_i=s_{i+b}\)
- 不妨设 \(b > a\)
- \(\forall i \in [1,n-b] s_i = s_{i+b} = s_{i+b-a}\)
- \(\forall i \in [n-b+1,n-b+a],s_i = s_{i-a} = s_{i-a+b}\) 所以能得到 \(n-b+1-a>=1\) 故能得到 \(a+b<=n\)
-
整周期性质
- 对于一个长度为 \(n\) 的字符串 \(s\)，求它的最小整周期
- 从大到小枚举 border 中的元素，若 \(n - k | n\) 则 \(n - k\) 是最小整周期
- 最小整周期要么是 \(n - fail(s)\)，不然就是 \(n\)
证明：
设 \(n - k\) 为最小整周期（k>0） 则 \(n-k<=\frac{n}{2}\) 易得 \(n-fail(s) <= \frac{n}{2}\) 故能得到 \(\gcd(n-k,n-fail(s)) = n-fail(s)\) 是周期，故可以得到 \(n-fail(s) | n - k\) 故最小整周期是 \(n - fail(s)\) 证毕。
-
border 构成 \(\log\) 段等差数列
- 若 border 长度 <= \(\frac{n}{2}\) \(n\) 归到 $ < \frac{n}{2}$
- 否则若 border 长度 \(> \frac{n}{2}\) 周期为 \(A\)，我们需要证明所有长度 \(>= \frac{n}{2}\) 的 border 构成等差数列，因为所有 \(<= \frac{n}{2}\) 的周期都是 \(A\) 的倍数，易得 \(A\) , \(2A\) , \(3A\) 构成等差数列。证毕
