Lyndon分解

发表于 分类于

一个似乎比较偏门的知识？

定义

  • Lyndon串：若某字符串中所有后缀字典序最小的是这个字符串本身，则这个串为 Lyndon串。
  • 近似Lyndon串：设 $t$ 是一个Lyndon串，$t^c$ 为 $t$ 拼接 $c$ 次，$t’$ 为 $t$ 串可空前缀，那么 $t^c+t’$ 为近似Lyndon串。
  • Lyndon分解：将一个字符串 $S$ 分解成一个字符串序列 $s_1,s_2\cdots s_m$，其中 $s_i$ 是Lyndon串，$s=s_1+s_2+\cdots+s_m$（+号表示拼接），且 $\forall i\in[1,m),s_i\geq s_{i+1}$。

定理

  • 若 $s,t$ 为Lyndon串，且 $s<t$ ，则 $st$ 为Lyndon串。
  • 对于一个字符串，Lyndon分解唯一。

第一个定理显然，第二个可以用反证法。

Duval 算法

考虑依次增加一个数。

维护三个指针 $i,j,k$。

表示 $[1,i)$ 的字母都已经在Lyndon分解里面了，现在在考虑 $i$ 及其后面的字母；$[i,k)$ 可以表示为 $t^c+t’$ 的形式（即近似Lyndon串）；$j=k-|t|$，即 $k$ 一个周期前的字母。

考虑第 $k$ 个字母。

分三种情况讨论：

  • $s_j=s_k$，那么可以继续接上去，$j,k$ 右移一位。
  • $s_j<s_k$，那么 $[i,k]=t^c+t’+s_k$ 就是一个新的Lyndon串，此时将 $j$ 设为 $i$，然后 $k$ 右移一位，考虑下一个 $k$。
  • $s_j>s_k$，那么只能 $c$ 个 $t$ 串作为新的Lyndon串，然后将 $i$ 设为 $t’$ 的开头，重新开始考虑，即 $j=i,k=i+1$。

时间复杂度 $O(n)$。

程序实现：

luogu模板题链接

1
2
3
4
5
6
7
8
9
10
11
12
13
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1,j,k;i<=n;)
	{
		j=i; k=i+1;
		for(;k<=n&&s[j]<=s[k];j=(s[j]==s[k++])?j+1:i);
		for(;i<=j;i+=k-j,ans^=(i-1));
	}
	printf("%d",ans);
	return 0;
}

最小表示法

一个字符串的最小表示为所有循环同构的串中，字典序最小的那个。

可以用Lyndon分解求出。将 $s+s$ 进行Lyndon分解。然后找到分解后Lyndon串首字母位置 $\le n$ 的最大的位置。从那个位置开始的就是最小表示。