来个简单的。
概念
- Lyndon 串：一个字符串 \(s\) 被称为 Lyndon 串，当且仅当 \(s\) 整个串是所有后缀中严格最小的。
例如 \(\mathtt{ababb},\ \mathtt{abcdefg}\)。
- Lyndon 分解：将字符串 \(s\) 分解为 \(w_1,w_2,...,w_k\)，满足 \(w_1 \ge w_2 \ge ... \ge w_k\)，并且 \(w_1,w_2,...,w_k\) 都是 Lyndon 串。
例如 \(\mathtt {acaababc}\) 可以分解为 \(\mathtt {ac,aab,abc}\)。
性质
① 对于 Lyndon 串 \(u,v\)，若 \(u<v\)，那么 \(uv\) 也是 Lyndon 串。
证明
-
若 \(u\) 不是 \(v\) 的前缀，那么一定有 \(uv<v\)。
-
若 \(u\) 是 \(v\) 的前缀，由于 \(v\) 是 Lyndon 串，那么 \(v\) 中以位置 \(|u|+1\) 开头的后缀 \(> v\)，进而知 \(uv<v\)。
② 一个字符串 \(s\) 的 Lyndon 分解存在且唯一。
存在性证明
令 \(w_1,w_2,...,w_{|s|}\) 分别为 \(s_1,s_2,...,s_{|s|}\)，这些串都是 Lyndon 串。
对于 \(i<|s|\)，如果 \(w_i < w_{i+1}\)，那么合并 \(w_i,w_{i+1}\)。由性质①可知，合并后的串仍是 Lyndon 串。
一直合并，最后一定有 \(w_1 \ge w_2 \ge ... \ge w_k\)。
唯一性证明
使用反证法，若 \(s\) 有两种 Lyndon 分解：
-
\(s = w_1w_2...w_{i-1}w_iw_{i+1}...w_k\)
-
\(s = w_1w_2...w_{i-1}w_i'w_{i+1}...w_j'...w_{k'}\)
钦定 \(|w_i| \ge |w_i'|\)，并且 \(w_i = w_i'w_{i+1}'...w_{j-1}'\text{pre}(w_j')\)。
那么 \(w_i \ge \text{pre}(w_j')\)，设 \(\text{pre}(w_j')\) 在 \(w_i\) 中的开头位置为 \(p\)，则 \(w_i \ge「w_i \text{ 中以位置 } p \text{ 开头的后缀}」\)
这与 \(w_i\) 是 Lyndon 串矛盾。
Duval 算法
Duval 算法以 \(O(n) - O(1)\) 的复杂度求出了一个字符串的 Lyndon 分解。
我们维护三个指针 \(i,j,k\)，把 \(s\) 分成三段，分别为 \(s_{1...i-1},s_{i...k-1},s_{k...n}\)。
同时维护 \(s_{i...k-1}\) 的一个周期 \(p=k-j\)，即 \(s_{i...k-1} = s_{i...i+p-1} ^ t + \text{pre} (s_{i...i+p-1})\)，并且 \(s_{i...i+p-1}\) 是 Lyndon 串。
使用增量法，目前考虑加入字符 \(s_k\)，分三种情况：
- \(s_j = s_k\)
周期 \(p\) 仍然合法，令 \(j\gets j + 1\)。
- \(s_j < s_k\)
可知 \(s_{i...k}\) 是一个 Lyndon 串，重新设置周期长度，令 \(j\gets i\)。
- \(s_j > s_k\)
本轮分解完毕，得到 Lyndon 串 \(s_{i...i+p-1},s_{i+p...i+2p-1},s_{i+2p,i+3p-1},...\)。
每轮开始时，令 \(j\gets i,\ k\gets i + 1\)。
点击查看代码
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define fi first
#define se second
#define pir pair <ll, ll>
#define mkp make_pair
#define pb push_back
using namespace std;
const ll maxn = 5e6 + 10, inf = 1e17;
char s[maxn];
ll n, ans;
int main() {
scanf("%s", s + 1); n = strlen(s + 1);
for(ll i = 1; i <= n;) {
ll j = i, k = i + 1;
while(k <= n && s[j] <= s[k]) {
if(s[j] == s[k]) ++j;
else j = i;
++k;
}
while(i <= j) {
ans ^= i + k - j - 1;
i += k - j;
}
}
printf("%lld", ans);
return 0;
}
这玩意可以直接求解最小表示法，这里懒得写了。
标签：...,text,Lyndon,ge,分解,小记,define From： https://www.cnblogs.com/Sktn0089/p/18185129