Lyndon分解 学习笔记

什么是 \(Lyndon\)

我们定义一个串是 \(Lyndon\) 串,当且仅当这个串的最小后缀就是这个串本身。

也就是说 \(Lyndon\) 串等价于这个串是它的所有循环表示中字典序最小的。

\(Lyndon\) 分解定义

将一个字符串 \(S\) 分解为若干个子串:\(s_1s_2s_3\dots s_m\)。对于任意 \(i\in [1,m]\),使得 \(s_i\)\(Lyndin\) 串,且 \(\forall i\in[1,m-1],s_i\ge s_{i+1}\)

一些性质

  • \(u,v\) 都为 \(Lyndon\) 串,且 \(u<v\),那么 \(uv\) 一定为 \(Lyndon\) 串。

证明
如果想要证明 \(uv\)\(Lyndon\) 串,就要证明 \(uv\) 是其最小后缀。

也就是只需要证明 \(uv<v\),由于 \(u<v\),那么显然成立。

  • 存在性

证明

我们可以吧所有字符单独成立一个字符串,然后根据上面那一条性质,我们可以不断找到 \(s_i<s_{i+1}\) 的,将这两个进行合并(合并之后还为 \(Lyndon\) 串),最后肯定能弄成所有 \(s_i\) 都是 \(Lyndon\) 串且 \(s_i\ge s_{i+1}\) 的。

  • 唯一性

证明
我们设有两种分解方式分别为:
\(s_1s_2s_3\dots s_{i-1}s_{i}s_{i+1}\dots s_m\)
\(s_1s_2s_3\dots s_{i-1}s_{i}'s_{i+1}'\dots s_k'\)

我们发现从第 \(i\)\(Lyndon\) 串开始两种分解方式开始不一样了,我们不妨设 \(s_i=s_i's_{i+1} 's_{i+2}'\dots s_p'[:l]\),其中 \(s_p'[:l]\) 表示第 \(p\) 个字符串的前 \(l\) 个字符组成的字符串。

我们可以因为 \(Lyndon\) 分解的定义推断出 \(s_i'\ge s_{i+1}'\ge s_{i+2}'\ge \dots\ge s_p'[:l]\)

那么因为 \(s_i'\)\(s_i\) 的前缀,那么 \(s_i'<s_i\),所以 \(s_i>s_i'\ge s_{i+1}'\ge s_{i+2}'\ge \dots\ge s_p'[:l]\)

然后又因为 \(s_i\) 也为 \(Lyndon\) 串(也就是说 \(s_i\) 是其所有子串中最小的),那么 \(s_i>s_i'\ge s_{i+1}'\ge s_{i+2}'\ge \dots\ge s_p'[:l] >s_i\)

\(s_i>s_i\) 显然不成立,所以分解是唯一的。

Duval算法

考虑分为三个部分:第一部分已经分解完的,第二部分正在分解的,第三部分还没分解的。

\(Duval\) 的算法思想是保证第二部分是 \(Lyndon\) 串的情况下,然第二部分的元素越多越好。

我们维护三个变量:\(i,j,k\)

\(S[1,i-1]=s_1s_2\dots s_q\) 表示已经固定下来的分解,其中 \(s_i>s_{i+1}\)

\(S[i,k-1]=|t|^p+v\) 表示是还没有确定下来的分解,对于循环的 \(|t|\) 他们一定是满足 \(t_i>t_{i+1}\) 的,所以把他们分在一起。

那么我们就能设当前第二部分开头的位置为 \(i\),要加入第二部分的指针为 \(k\)\(j\)\(|t|\) 这个循环中的,将 \(j\)\(k\) 这两个位置上的字符进行比较,那么:

  • \(s_k=s_j\) 时,没有什么问题,直接匹配下一个字符。

  • 当 $s_k>s_j $ 时,加入的字符后第二部分还是一个 \(Lyndon\) 串。

  • 当 $s_k<s_j $ 时,\(t_1,t_2\dots t_h\) 的分解被固定下来,算法从 \(v\) 重新开始。

Code

洛谷P6114 【模板】Lyndon 分解

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch;
	ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-f;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+(ch-'0');
		ch=getchar();
	}
	return x*f;
}
int main(){
	int n,ans=0;
	char s[5000005];
	scanf("%s",s+1);
	n=strlen(s+1);
	int i=1;
	while(i<=n){
		int j=i,k=i+1;
		while(k<=n&&s[j]<=s[k]){
			if(s[j]==s[k]) ++j;
			else j=i;
			++k;
		}
		for(;i<=j;i+=(k-j))
			ans^=(i+k-j-1);
	} 
	printf("%d",ans);
	return 0;
}

热门相关:我有一座冒险屋   异世修真邪君   本法官萌萌哒   本法官萌萌哒   不科学御兽