This is not the end.

0%

Lyndon word 与 Duval 算法

Posted on

下文中的字符串大小比较都是字典序的比较。

Lyndon word

对于一个字符串$s$，$s$小于$s$的所有后缀，那么$s$就是一个Lyndon word。

显然此时$s$也小于$s$的所有循环移位。

Lemma 1

对于两个Lyndon word$u,v$满足$u<v$，那么$uv$也是一个Lyndon word。

Lemma 2

如果一个Lyndon word$s$后面接一个字符$c$得到的字符串$sc$是某个Lyndon word的前缀（即满足$s$小于等于所有的后缀），那么对于任意一个$x>c$，$sx$是Lyndon word。

Lyndon 划分

定义字符串$s$的Lyndon划分为：$s=t_1t_2t_3\cdots t_m$，其中$t_i$均为Lyndon word且有$t_i \ge t_{i+1}$。

一个字符串的Lyndon word存在且唯一。

存在性证明

首先把$s$的每个字符单独划为一段，此时显然每一段都是Lyndon word。

如果相邻的两段满足$t_i<t_{i+1}$，那么把这两段合并起来仍然得到Lyndon word。

一直合并直到对于所有$i$都有$t_i \ge t_{i+1}$，此时我们就得到了一个Lyndon划分。

唯一性证明

设$s$的两个Lyndon划分分别为$t_1t_2\cdots t_m$和$t’_1t’_2\cdots t’_{m’}$，设第一个$i$为最小的满足$t_i \not=t’_i$的下标。设$|t_i|\le |t’_i|$，那么$t_i$一定是$t’_i$的前缀。设$t’_i$去掉$t_i$的那一段后缀为$x$，则因为$t$是Lyndon划分，所以$t_i \ge x$，又因为$t’$是Lyndon划分，所以$t’_i < x$，则得到$t_i \ge x > t’_i > t_i$，矛盾。所以一个串的Lyndon划分是唯一的。

Duval 算法

一种线性构造Lydon划分的算法，本质上是用类似单调栈的思想模拟合并的过程。

维护三个指针$i,j,k$，其中$s[1\cdots i-1]$的Lyndon划分已经确定，$s[i\cdots k]$的形式为$t^m v$，其中$t$为Lyndon串，$v$是$t$的一个前缀，$j=k-|t|$。

考虑$k+1$这个字符：

1. s[k+1] = s[j+1] 让j,k自增1即可
2. s[k+1] > s[j+1] 此时s[i……k+1]是一个Lyndon串，让j=i，k自增1即可
3. s[k+1] < s[j+1] 此时s[i……k-|v|]无法再合并，这一段中的每一个t就是这一段的Lyndon划分。记录下这个划分，令i=k-|v|+1,j=i,k=i+1

模板：loj129

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
template <class T>
inline void rd(T &x) {
	x=0; char c=getchar(); int f=1;
	while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }
	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int N=(1<<20)+10;
char str[N];
int n;
int main() {
	scanf("%s",str+1); n=strlen(str+1);
	int i=1,j,k;
	while(i<=n) {
		j=i,k=i+1;
		while(k<=n&&str[k]>=str[j]) {
			if(str[k]==str[j]) ++k,++j;
			else j=i,++k;
		}
		while(i<=j) {
			printf("%d ",i+(k-j)-1);
			i+=k-j;
		}
	}
	return 0;
}