字符串的Period(周期), Border
字符串的Period(周期), Border
前置知识：\(\text{kmp}\)，\(\text{AC}\) 自动机
约定：字符串 \(S\) 的长度为 \(|S|\)，原串的长度为 \(n\)，\([l,r]\) 的子串为 \(S_{l,r}\)，下标从 \(1\) 开始，前缀 \(S_{1,i}=pre_i\)，后缀 \(S_{i,n}=suf_i\)，设\(S\) 的 \(\text{Border}\) 集合为 \(B(S)\)，设最长的 \(\text{Border}\) 为 \(\text{LBorder}\)。
\(\text{Border}\):
定义字符串 \(S\) 的一个 \(\text{Border}\) 为一个满足 \(pre_i=suf_{n-i+1}\) 的前缀，\(S\) 和 \(\emptyset\) 也是一个 \(\text{Border}\)。
\(\text{kmp,AC}\) 自动机的 \(fail\) 指针均指向当前串的 \(\text{LBorder}\)。
\(\text{Period}\) （周期）:
若 \(\exists |T|\in B(S), 2|T|\ge n\)，则 \(S\) 的一个周期是 \(n-|T|+1\)。
\(\text{Periodicity Lemma}:\)
若 \(p,q\) 是 \(S\) 的周期，且 \(p+q+\gcd(p,q)\leq |S|\)，则 \(\gcd(p,q)\) 也是 \(|S|\) 的一个周期。
关于 \(\text{Border}\) 的推论：
\(B(S)=B(\text{LBorder})\cup\{S\}\)，
串 \(S\) 的所有 \(\text{Border}\) 长度构成了不超过 \(\log n\) 个等差数列。
证明：
如果\(S\)的\(\text{LBorder}\)，设其为\(T\)满足\(2|T|\ge |S|\)，则所有\(R\in B(S),2|R|\ge |S|\)形成了一个等差数列
参过下面这张图
则长度为 \(|T|-(|S|-|T|)\)，即标为红色的那一段，它也是原串的一个 \(\text{Border}\)。
更简洁的解释是，\(S\) 有着长度为 \(|S|-|T|\) 的周期。
所以实际上不止是 \(2|R|\ge |S|\) 的串，而是所有 \(\forall|R|\equiv |S|\pmod {|S|-|T|}\) 的 \(R\) 都是 \(S\) 的 \(\text{Border}\)。
这样的失配过程就可以归纳为：
每次 \(mod\) 最短周期 \(|T|-|S|\)，而取模使得长度至少减半，故可以分成\(\log n\) 段等差数列。
\[ \ \]
并且任意一段最大项为 \(x\)，差为 \(d\) 的等差数列，最小项是 \(x\mod d+d\) 。
(\(+d\) 是因为在 \(x\mod d+d\) 下一次可能跳的位置 \(>x\mod d\))
应用：对于 \(\text{kmp,AC}\) 自动机的字符集过大导致无法存储每种字符的转移，而又有类似可持久化的匹配操作时，
直接暴力跳 \(fail\) 会导致复杂度退化，但是可以用等差数列的性质来快速跳。
每次形成等差数列时，周期中失配位置的下一个字符都相同。
故如果在等差数列上失配，可以直接通过对于差值取模快速跳过，以保证复杂度为 \(O(\log n)\)。
相比于倍增处理，这样跳常数小，实现简单。
具体看下面的习题代码。
练习模板: Luogu P5829 求公共 \(\text{Border}\)。
1 |
|