Lyndon 串

你说得对，但是这个是\(\Large{\textsf{巨大}}\)浓缩版。非浓缩版作者并没有写完。作者删掉了所有的证明，居心不良。

定义：\(S\) 是 Lyndon 串（Lyndon word）当且仅当 \(S\) 是所有后缀中最小的。也当前仅当 \(S\) 比所有他的其他 cyclic-shift 都小。

性质：Lyndon 串 无非空的 border。证明：假设有非空 border，则 \(S=aba\)，则 \(aab\) 一定更小。

引理 1：\(u,v\) 是 LW，若 \(u<v\)，则 \(uv\) 也是 Lyndon 串。

定义一个串分解成 Lyndon 串的标准形式为标准分解。

标准分解：将 \(S\) 划分成若干个 Lyndon 串 \(w_1\sim w_k\)，使得 \(w_1\ge w_2\ge \cdots \ge w_k\)。

性质：一个字符串得 Lyndon 分解存在。

性质：一个字符串得 Lyndon 分解唯一。

Duval 算法

引理 2：\(c<c'\)，\(vc\) 是某个 LW 的前缀，$vc'\in $ LW。

维护三个指针：\(i,j,k\)，其中 \(S[1,i-1]\) 已经分解完毕，\(S[i,k-1]\) 是形如 \(w^xw'\) 的串（\(w'\) 是 \(w\) 的可空真前缀，\(w\) 是 LW），\(j\) 是 \(k-|w|\)。\(k\) 是下一个我们要加入的字符。\(i\sim k-1\) 中有一个长度为 \(|u|=k-j\) 的周期。

一共有三种情况：

• \(S_j=S_k\)。那么我们的周期可以保持不变，\(j\gets j+1,k\gets k+1\)。
• \(S_j<S_k\)。由引理 2 可知 \(w^xw'S_k\) 是一个 LW，因此合并他们为 \(w\)。
• \(S_j>S_k\)。这样 \(w^x\) 已经确定下来了，分解中多出 \(x\) 个 \(w\)，然后重新回到 \(w'\) 的开头分解。

while (i<n){
    int j=i,k=i+1;
    while (k<n && s[j]<=s[k]){
        if (s[j]<s[k]){
            j=i;
        }
        else{
            j++;
        }
        k++;
    }
    while (i<=j){
        ans^=i+k-j;
        i+=k-j;
    }
}

正确性：分解后 \(w_1\ge w_2\ge \cdots \ge w_k\)。证明：我们每一次跳出内层第一个 while 循环一定是出现了 \(S_j>S_k\)，这个时候 \(w^xw'\) 里面的 \(w\) 一定是大于 \(w'+S_k\) 的，则 \(w>w'+S_k+t\)，\(t\) 是任意字符串。也就是说最开始就保证了上一个（外层）循环内的 \(w\) 大于这一个的。

复杂度：观察程序，\(i\) 是单调向右移动的，而 \(k\) 每一次移动的距离不会超过 \(i\) 的距离，因此时间复杂度是 \(\mathcal{O}(n)\) 的。

应用：最小表示法

如何计算一个串 \(S\) 的最小表示？\(SS\) 的分解中，从开头 \(\le n\)，结尾 \(>n\) 的分解开始是最优的。