本原词与唯一重复根

为什么最短根是唯一的 ​

假设 $s=u^a=v^b$，而 $u,v$ 都本原。若 $a=1$，则 $s=u$ 已经本原，只能有 $b=1$，于是 $u=v$；另一边同理。因此只需考虑 $a,b\ge 2$。

令 $p=|u|,q=|v|,n=|s|$。二者都是 $s$ 的周期，且 $p,q\le n/2$，所以

Fine–Wilf 引理理路Fine–Wilf 周期引理Fine–Wilf theorem · Periodicity lemma · Fine-Wilf周期定理长度至少为 p+q−gcd(p,q) 的有限词若同时具有周期 p、q，就必有周期 gcd(p,q)。说明 $d=gcd(p,q)$ 也是周期。由于 $d$ 整除 $p,q$，前缀 $u$ 和 $v$ 都是同一个长 $d$ 块的整数次幂。它们本原，迫使 $p=q=d$，而它们又是 $s$ 的等长前缀，所以 $u=v$。根的长度相同后，指数 $a=b=n/p$ 也确定了。

这还说明所有完整根的长度都是本原根长度的倍数。若 $s=t^m$，先把 $t$ 拆成本原根 $r^{\prime }$ 的幂，那么 $s$ 也成为 $r^{\prime }$ 的幂，唯一性迫使 $r^{\prime }=r$。它不是只保证“最短长度唯一”，还保证内容和所有更长根的结构。

边界与迁移 ​

空词被排除，因为 ${\epsilon }^k=\epsilon$ 对任意正整数 $k$ 都成立，指数失去唯一性。允许空词作为根还会把所有长度论证破坏；本页的实现因此直接拒绝空输入。

本原性对旋转保持不变。如果一个旋转等于 $v^k$，把切口移回去，只会把重复块 $v$ 也旋转，原串仍是某个同长度块的 $k$ 次幂。这为循环移位等价类理路词的共轭与循环移位Conjugate words · Cyclic rotation of a word · Circular string · 词的旋转等价把词切为 uv 再连接成 vu 定义旋转等价；本原根的长度决定不同旋转的个数和相同旋转起点的间隔。提供了稳定的属性。但不同旋转的本原根内容可以不同，例如 bbaa 与 aabb 都本原，且互为旋转。

最后自行核验 abcabcabcabc、abcab 与 aaaaa。答案依次是 abc 的四次幂、整串的一次幂、a 的五次幂。给第二个答案时，应同时报告最短周期三并解释 $3\nmid 5$；给第三个答案时，应注意不同起点虽然有五个，旋转得到的字符串却只有一种。后一种重复计数将在下一页解决。

从最短周期得到本原根 ​

先用前缀函数理路前缀函数Prefix function · Failure function记录每个前缀的最长真前缀—后缀重合长度的字符串函数。算

这是最短周期理路字符串的周期与 borderPeriod of a word · Border of a word · 字符串周期 · 前后缀重合用错位后仍相等的位置定义有限字符串的周期，并把长度 p 的周期与长度 n-p 的前后缀重合一一对应。。若 $p\mid n$，则 $s=(s[0:p]{)}^{n/p}$；这个根必本原，否则还能得到更短周期。若 $p\nmid n$，本原根就是 $s$ 自己，指数为一。

第二个分支值得证明，不能只当口诀。假设 $p\nmid n$，但 $s$ 仍有一个真完整根，长度为 $q\mid n$、$q\le n/2$。最短周期满足 $p\le q$，因此长度条件足够，Fine–Wilf 给出周期 $gcd(p,q)\le p$。最短性迫使 $gcd(p,q)=p$，从而 $p\mid q\mid n$，与假设矛盾。所以不存在真完整根。

对于 bbaabbaabbaa，前缀函数为

最后一项为八，$p=12-8=4$；四整除十二，输出根 bbaa、指数三。对 abababa，$p=2$ 却不整除七，输出根仍是整串、指数一。两个分支都用到周期与整除，不能只保留其中一个条件。

def primitive_root(s):
    if not s:
        raise ValueError("the empty word has no primitive root")
    pi = [0] * len(s)
    for i in range(1, len(s)):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    p = len(s) - pi[-1]
    if len(s) % p:
        p = len(s)
    return s[:p], len(s) // p

循环不变量和线性比较次数由前缀函数的失败链证明提供；本页新增的逻辑是最后的整除分支及其正确性。算法使用 $O(n)$ 时间和 $O(n)$ 个整数单元，复制返回根还需 $O(|r|)$ 个字符。若只返回长度和指数，可以不复制根，但前缀数组仍占线性空间。

两块可以交换，意味着什么 ​

一般连接不满足交换律：ab 接 a 得 aba，交换后是 aab。不过两个非空词满足 $uv=vu$，当且仅当它们是同一个非空词的幂。[1]

“同根所以交换”直接来自指数相加。反向可以模仿欧几里得算法。若 $|u|\ge |v|$，从 $uv=vu$ 的前 $|v|$ 个字符看出 $u=vx$。代入并消去相同前缀，得到 $xv=vx$。当 $x$ 非空时，问题总长度缩短，继续归纳；当 $x$ 为空时，$u=v$，已经找到共同块。归纳返回的共同块同时生成 $v$ 和 $x$，因此也生成 $u=vx$。

例如 abab 和 ab 相交换，第一步消去一个 ab，剩下 ab 与 ab。这个结论用于排除“看似不同、实际同一重复块”的歧义；它并不说任何有共同前缀的两块都能交换。