题解：P6114 【模板】Lyndon 分解

· · 题解

P6114 【模板】Lyndon 分解

题意

我们定义一个字符串是 Lyndon Word，当且仅当当且仅当它严格小于它的所有非平凡后缀，即字典序最小的后缀是它本身。

给定一个字符串 s，要求一个将 s 分解为若干个字典序不降的 Lyndon Word，求分解后的所有右端点的异或和。

例如样例 ababa，一个合法的划分是 ab（非平凡后缀为 b，严格大于 ab）、ab、a（没有非平凡后缀）。

所有答案是 2\oplus4\oplus5=3。

*注：“非平凡后缀”指“非空真后缀”。

Duval 算法

求解 Lyndon 分解问题可以使用 Duval 算法。

我们将 s 分为 3 个部分：已确定的 Lyndon 分解、当前近似的 Lyndon 串、未处理部分，我们用 3 个指针 i,j,k 分别维护当前处理段的起始位置，当前 Lyndon 串中正在比较的位置，待加入字符的位置（当前扫描到的位置）。枚举 k ，每次比较 s_j 和 s_k 即可。

考虑 Lyndon 串定义，s_j 和 s_k 的大小只有以下 3 种情况：

显然对于每个 s_i 只会计算一次，时间复杂度 O(n)。

由上述过程也可以看作是“任意字符串的 Lyndon 分解是唯一确定的”的构造性证明，读者可以自行思考。

代码

#include<bits/stdc++.h>
#define N 5000010
using namespace std;
typedef long long LL;
//十年OI一场空，不开long long见祖宗
char s[N];
int main(){
    //freopen(".in" , "r" , stdin);
    //freopen(".out" , "w" , stdout);
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    int ans = 0;
    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 += 1;     
            k += 1;
        }
        while(i <= j){
            ans ^= (i + k - j - 1);
            i += (k - j);
        }
    }
    printf("%d\n", ans);
    return 0;
}