字符串的周期与 border

录下一段设备日志，得到 abababa。它看起来按 ab 重复，但长度为七，末尾只留下半个 ab。如果把“有周期”解释成“由某一整块重复若干次”，这段日志就会被误判。有限字符串的周期允许最后一块没有录完；整块重复还要额外检查长度能否整除。

本页先把这两个问题分开，再说明为什么已经学过的前缀函数能够在线性时间找出最短周期。所有下标从零开始，切片 $s[l:r]$ 包含 $l$ 、不包含 $r$ 。

形式陈述

移动几格后，重叠部分仍然相同

设非空字符串 $s$ 长度为 $n$ 。整数 $p$ 满足 $1\le p\le n$ ，且

s[i]=s[i+p]\qquad(0\le i<n-p),

就称 $p$ 是 $s$ 的一个周期。把同一条字符串右移 $p$ 格，两份记录重叠的位置必须逐个相等。 $p=n$ 时没有需要比较的位置，条件自动成立，称为平凡周期；所以每个非空字符串至少有一个周期。

对 abababa， $p=2$ 要比较五对位置： $(0,2),(1,3),(2,4),(3,5),(4,6)$ ，依次得到 a=a,b=b,a=a,b=b,a=a，全部通过。 $p=3$ 第一对就是 a 与 b，立即失败。把 $1$ 到 $7$ 全部检查一遍，周期集合是 $\{2,4,6,7\}$ 。

一个周期不要求所有字符相同，也不要求 $p$ 整除 $n$ 。它只约束相距 $p$ 、而且同时位于记录内的字符。更准确地说，若 $p$ 是周期，则

s[i]=s[i\bmod p]\qquad(0\le i<n).

证明是反复减去 $p$ ，每次都沿一对已知相等的位置移动。因此 $s$ 是无限重复 $s[0:p]s[0:p]\cdots$ 的一个前缀；“最后可能截断”正好体现在这里。

直觉

border 是同一份证据的另一种写法

长度 $b$ 满足 $0\le b<n$ ，并且

s[0:b]=s[n-b:n],

就称这段共同内容是一个真 border。这里允许 $b=0$ ，即空 border，但排除整个字符串。abababa 的非空 border 是 a、aba、ababa，长度分别为 $1,3,5$ 。

周期公式可以直接改写成

s[0:n-p]=s[p:n].

右边恰好是长度 $n-p$ 的后缀，因此

\boxed{p\text{ 是周期}\iff n-p\text{ 是真 border 的长度}.}

这是一一对应的数学关系，不是说“周期”和“border”是两个同义名。前者是位移长度，后者是重合内容；同一实例中的数值还互为补数。

abababa 右移两位后的重合长度为五，对应前后缀 ababa；周期二不整除长度七 — 位移 p 与重合长度 n-p

对应关系立即给出最短周期：最长 border 留下的位移最短。若最长真 border 长为 $b_{\max}$ ，则最短周期为 $p_{\min}=n-b_{\max}$ 。对 abababa，最长 border 长五，最短周期便是二。

例子与边界

从周期到整块重复，还差哪一步

abababa 的最短周期是二，但它不是 ab 的整数次幂。abababab 则长八，可以写成 $(\texttt{ab})^4$ 。对于给定周期 $p$ ，只有 $p\mid n$ 时，前面的逐位置等式才能拼成

s=(s[0:p])^{n/p}.

另一个容易混淆的例子是 abaaba：它有周期三和五，却没有周期 $\gcd(3,5)=1$ 。两个周期的最大公约数并不总是周期。Fine–Wilf 周期引理会给出记录足够长时的准确门槛；不满足门槛时，不能直接把两个位移合并。

“有非空 border”也不等于“不是本原词”。aba 的 border 是 a，周期是二，但它不是任何更短非空串的整数次幂，仍是本原词。无 border 一定本原；反方向不成立。

本页把空字符串单独留在接口边界：没有 $1\le p\le n$ 的候选，最短正周期未定义。实现可以返回 None，也可以按应用另定约定，但不能直接读取 $\pi[-1]$ 。允许 $p>n$ 的教材约定会多出一批空约束周期，不影响非空字符串的最短周期；本页将它们排除，以便周期和真 border 保持一一对应。

手算检查与迁移

给定 abcabca，先不用算法逐项检查 $p=3$ ，再写出对应的 border。七个字符中要比较四对位置，全部相等，border 是长四的 abca；其最长 border 也为四，所以最短周期是三。 $3\nmid7$ ，不能据此声称记录包含整数个 abc。

现在把记录改为 abcabc。最短周期仍为三，但长度变为六，于是确实是两个 abc。这两条记录可能来自同一循环设备，只是截取长度不同：周期识别负责找重复规律，本原根识别负责找整块分解，循环串规范化还要处理从哪个位置开始记录。后三个问题会在后续页面逐步分开解决。

推论与应用

用已经算过的重合信息求周期

前缀函数 $\pi[i]$ 保存 $s[0:i+1]$ 的最长真 border 长度。因此只需求一次前缀函数，就有

p_{\min}=n-\pi[n-1].

例如 abababa 的数组是 $[0,0,1,2,3,4,5]$ ，最后一项给出 $7-5=2$ 。这里使用的是最后一项，不能把整个数组中的最大值不加说明地当作整串 border。

要列出全部周期，可以顺着 border 链走：先输出 $n$ ；再从 $b=\pi[n-1]$ 开始，依次输出 $n-b$ ，并令 $b\leftarrow\pi[b-1]$ ，直到 $b=0$ 。前缀函数页已经证明，这条链恰好列出全部非空真 border，不会漏掉夹在两个长度之间的候选。结果的输出顺序不一定递增，需要有序列表时再按对应方向组织。

Z 函数提供另一种检查方式。对 $1\le p<n$ ， $Z[p]=n-p$ 当且仅当 $p$ 是周期，因为这正好比较 $s[p:n]$ 和等长前缀。已拥有 Z 数组时，没有必要为了同一查询重新构造前缀函数。

构造前缀函数或 Z 数组需 $O(n)$ 次常数成本字符比较，占 $O(n)$ 个整数单元；之后取最短周期只需 $O(1)$ 时间。全部周期可能有 $n$ 个，例如 aaaa，所以报告全部答案本来就可能需要线性输出。字符若是大型对象，须把一次相等比较的实际代价乘进去。

参考资料

M. Lothaire, Combinatorics on Words, Cambridge University Press, 1997，§1.3 “Conjugacy and periodicity”：有限词的周期、border 与幂。本文的两个日志实例独立构造。
Dan Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997，第1章：前缀重合的线性预处理。
Štěpán Holub, Martin Raška and Štěpán Starosta, Combinatorics on Words Basics, Archive of Formal Proofs, 2021；CoWBasic、Border_Array：border、周期与根的形式化接口。

形式陈述 ​

移动几格后，重叠部分仍然相同 ​

border 是同一份证据的另一种写法 ​

从周期到整块重复，还差哪一步 ​

手算检查与迁移 ​