题解 P6127 【【模板】Lyndon 分解】

wucstdio · 2020-02-18 16:33:06 · 题解

大概是我贡献的第二道模板？

\text{Lyndon} 分解详解

我们定义一个串是 \text{Lyndon} 串，当且仅当这个串的最小后缀就是这个串本身。

该命题等价于这个串是它的所有循环表示中字典序最小的。

引理 1：如果 u 和 v 都是 \text{Lyndon} 串并且 u<v，则 uv 也是 \text{Lyndon} 串。

证明：

1、若 \operatorname{len}(u)\ge\operatorname{len}(v)

这时，u 和 v 这两个串在 \operatorname{len}(v) 之前就出现了不同的字符，所以有 v>uv，又因为 v 是 \text{Lyndon} 串，所以 v 的所有后缀都大于 v，所以 uv 的所有后缀都大于 uv，故 uv 是 \text{Lyndon} 串。

2、若 \operatorname{len}(u)<\operatorname{len}(v)

若 u 不是 v 的前缀，那么有 v>uv，得证。

若 u 是 v 的前缀，那么如果 v<uv，则必有 v[\operatorname{len}(u)+1:]<v（也就是各自去掉了前 |u| 个字符），矛盾。

我们定义一个串 S 的 \text{Lyndon} 分解为一个字符串序列 A_1,A_2,\dots,A_m，满足：

可以证明这种划分存在且唯一。

存在性证明

初始令 m=|S| 并且 A_i=S[i]，然后每次不断找到 A_i<A_{i+1} 并且合并为一个串。最后一定能使得所有的 A_i\ge A_{i+1}。

唯一性证明

假设对于字符串 S 存在两个 \text{Lyndon} 分解：

S=A_1A_2\cdots A_iA_{i+1}A_{i+2}\cdots A_{m_1}

S=A_1A_2\cdots A_iA^\prime_{i+1}A^\prime_{i+2}\cdots A^\prime_{m_1}

不妨设 \operatorname{len}(A_{i+1})>\operatorname{len}(A^\prime_{i+1})。

观察 A_{i+1} 在第二种分解中的对应情况。假设 A_{i+1}=A^\prime_{i+1}A^\prime_{i+2}\cdots A^\prime_{k}A^\prime_{k+1}[:l]。

那么由 \text{Lyndon} 串的性质可知：

A_{i+1}<A^\prime_{k+1}[:l]\le A^\prime_{k+1}\le A^\prime_{i+1}<A_{i+1}

矛盾。

引理2：若字符串 v 和字符 c 满足 vc 是某个 \text{Lyndon} 串的前缀，则对于字符 d>c 有 vd 是 \text{Lyndon} 串。

证明：

设该 \text{Lyndon} 串为 v+c+t。

则 \forall i \in [2,|v|],v[i:]+c+t>v+c+t，也就是说 v[i:]+c\ge v。

所以 v[i:]+d>v[i:]+c\ge v。

同时因为 c>v[1]，我们有 d>c>v[1]。

故 v+d 是一个 \text{Lyndon} 串。

\text{Duval} 算法

这个算法可以在 O(n) 时间复杂度，O(1) 空间复杂度内求出一个串的 \text{Lyndon} 分解。

该算法中我们仅需维护三个变量 i,j,k。

维持一个循环不变式：

s[i,k-1]=t^h+v(h>1)$ 是没有固定的分解，满足 $t$ 是 $\text{Lyndon}$ 串，且 $v$ 是 $t$ 的可为空的不等于 $t$ 的前缀，且有 $s_g>s[i,k-1]

如下图：

当前读入的字符是 s[k]，令 j=k-|t|。

分三种情况讨论：

当 s[k]=s[j] 时，直接 k\leftarrow k+1,j\leftarrow j+1，周期 k-j 继续保持
当 s[k]>s[j] 时，由引理 2 可知 v+s[k] 是 \text{Lyndon} 串，由于 \text{Lyndon} 分解需要满足 s_i\ge s_{i+1}，所以不断向前合并，最终整个 t^h+v+s[k] 形成了一个新的 \text{Lyndon} 串。
当 s[k]<s[j] 时，t^h 的分解被固定下来，算法从 v 的开头处重新开始。

复杂度分析：i 只会单调往右移动，同时 k 每次移动的距离不会超过 i 移动的距离，所以时间复杂度是 O(n) 的。

代码如下：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
char s[5000005];
int n,ans;
int main()
{
    scanf("%s",s+1);
    n=(int)strlen(s+1);
    for(int i=1;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)//从v的开头重新开始
        {
            ans^=i+k-j-1;
            i+=k-j;
        }
    }
    printf("%d\n",ans);
    return 0;
}