Fine–Wilf 周期引理

短一位为什么真的不够 ​

把长度六的 abaaba 标上位置 $0,1,2,3,4,5$。周期三要求

周期五只要求 $0\sim 5$。把必须相等的位置连边，得到两个连通块：$\{0,2,3,5\}$ 和 $\{1,4\}$。分别填 a、b，所有已要求的等式成立，却保留了两种字符。

当长度增加到七时，周期三新添边 $3\sim 6$，周期五新添边 $1\sim 6$。这两条边把两个块接通，于是所有位置必须相同。门槛 $3+5-1=7$ 不是从公式里猜出的数字，它恰好阻止这个反例。

这组实例证明的是：不能把对所有 $p,q$ 都有效的门槛统一减一。某些特殊参数本来就有更强结论，例如 $p\mid q$ 时，最大公约数就是已知周期 $p$，不需要再借定理推出。

先证明一个传递规则 ​

后面会把问题缩短，所以先说明如何从一段子串把周期传回整串。

设 $s$ 有周期 $p$，其中一段长度至少为 $p$ 的连续子串有周期 $d$，而且 $d\mid p$。那么整串都有周期 $d$。

理由是这段子串覆盖了模 $p$ 的每一种余数。整串任何位置 $i$ 都能沿 $p$ 格等式，移动到子串中一个同余位置 $i^{\prime }$，所以 $s[i]=s[i^{\prime }]$。两个模 $d$ 同余的位置被送到子串后仍模 $d$ 同余，因为 $d\mid p$；子串里的 $d$ 周期使它们字符相同。于是整个字符串中相距 $d$ 的位置也相同。[2]

“子串足够长”和“$d$ 整除 $p$”都参与了证明。只在某个很短角落看到连续 aa，当然不能让一条任意长的 $p$ 周期记录变成常字符。

用减法版欧几里得算法证明 ​

对 $p+q$ 作强归纳理路强归纳法Strong induction · Complete induction归纳步可假设所有较小自然数情形成立。。不妨 $p\le q$。若 $p=q$，结论就是已经知道的周期 $p$。以下设 $p<q$，仍记 $d=gcd(p,q)$。

取前缀 $t=s[0:n-p]$。它保留周期 $p$；它还有周期 $q-p$。对每个 $0\le i<n-q$，

第一个等式用周期 $q$，第二个用周期 $p$。这恰好覆盖了 $t$ 中所有相距 $q-p$ 的位置，所以周期检查既不越界，也没有遗漏。

新问题满足同一种长度门槛：

而 $p+(q-p)=q<p+q$，归纳假设可以应用，得到 $t$ 有周期 $d$。这里的最大公约数保持不变，正是欧几里得算法理路整数欧几里得算法Euclidean algorithm for integers反复使用带余除法计算最大公约数的有限算法。减去较小数时使用的性质。

最后要把结论传回被删去的尾部。由于 $p,q$ 都是 $d$ 的倍数且 $q>p$，有 $q\ge p+d$，所以

前缀足以覆盖所有模 $p$ 的位置，又有 $d\mid p$，上一节的传递规则适用，整串因此具有周期 $d$。证明到此闭合；不能只证明缩短后的前缀就把原串尾部略掉。

终点检查：拒绝一个貌似合理的合并 ​

某程序对长度七的 aaabaaa 报告周期四和六，随后把周期改成二。先核验原报告：四格比较是位置 $0/4,1/5,2/6$，都为 a；六格只比较 $0/6$，也相等。但两格比较 $1/3$ 是 a 对 b，失败。

错误恰好在长度条件：$4+6-gcd(4,6)=8$，七个字符少一位。把实例画成约束图，会得到偶数位置块、$\{1,5\}$ 和孤立位置 $3$；这个尚未连上的位置容许 b 存在。能指出哪一对比较失败，比只说“定理条件不满足”更接近一个可用的程序反例。

怎样把定理用在算法里 ​

假设一个重复检测程序分别发现同一片段有周期 $p$ 和 $q$。安全的合并过程是先确认这两个周期针对的是同一连续片段，再计算 $d$，最后检查该片段长度是否至少 $p+q-d$。满足时才可把两个周期压缩为 $d$。

若周期来自不同窗口，需要先把它们限制到共同重叠区间，并按那个区间的长度检查门槛。不能用两个窗口长度之和替代重叠长度，也不能把两组零散采样点当成一段连续记录。

已知周期确实成立时，计算门槛只需一次 gcd 与常数次整数操作；在机器字模型中，普通欧几里得算法使用 $O(\log min(p,q))$ 次除法。若输入只是“声称有两个周期”，还要逐字符核验，成本为 $O(n)$，定理本身不会免费证明输入承诺。处理大整数位串时则另计除法的位成本。

还有一个重要用途是本原根理路本原词与唯一重复根Primitive word · Primitive root of a word · 本原字 · 字符串本原根不能写成更短非空词的二次或更高整数幂的词称为本原词；每个非空词都能唯一写成本原根的正整数幂。。如果同一个词既是长度 $p$ 块的整数次幂，又是长度 $q$ 块的整数次幂，整块重复提供足够长的重叠。周期引理会迫使它们服从共同的更短块，从而保证最短根唯一。