Lyndon分解学习小记

参考资料：

https://www.luogu.com.cn/blog/wucstdio/solution-p6127

https://oi-wiki.org/string/lyndon/

因为有参考资料所以这里不写详细。

Lyndon串：如果一个串是Lyndon串，当且仅当所有后缀中字典序最小的串是这个串本身。

另一个定义：所有循环同构串中字典序最小的串是这个串本身。两者等价。

Lyndon分解：将一个字符串(s)分解成(s_1s_2dots s_k)，满足(s_1ge s_2ge dotsge s_k)，并且(s_i)为Lyndon串。Lyndon分解存在且唯一。

引理1：如果有两个串(u,v)为Lyndon串，且(u<v)，则(uv)为Lyndon串。

引理2：如果存在串(v)和字符(c)满足(vc)为某个Lyndon串的前缀，则如果有字符(d>c)，(vd)为Lyndon串。

这里有证明：https://www.luogu.com.cn/blog/wucstdio/solution-p6127

Duval 算法

现在把字符串分成三个部分：(S_1S_2S_3)。

其中(S_1)已经完成Lyndon分解，(S_2)为Lyndon近似串，即可以分解成：(wwwdots wv)，(w)为Lyndon串，(v)为(w)的前缀。

有三个指针(i,j,k)，其中(S_1=[1,i-1],S_2=[i,k-1])，(j=k-|w|)。

现在尝试将(s_k)加入(S_2)中，考虑指针的变化：

如果(s_k=s_j)，则(j)和(k)分别后移。
如果(s_k>s_j)，根据引理2有(vs_k)为Lyndon串。再根据引理1，它要和前面的若干个(w)合并。也就是说(S_2s_k)合并成一个Lyndon串，成为新的(S_2)，即(jleftarrow i)。（此时只是表明它们合并成了Lyndon串，并不表明它们已经分解好，所以没有归到(S_1)）
如果(s_k<s_j)，把(S_2)的前缀（若干个(w)）丢入(S_1)中，留下(v)。(i)位置变更，(kleftarrow i+1)，(jleftarrow i)。

具体见代码（洛谷模板）：

using namespace std;
#include <bits/stdc++.h>
#define N 5000005
int n;
char s[N];
int q[N],cnt;
int main(){
	freopen("in.txt","r",stdin);
	scanf("%s",s+1);
	n=strlen(s+1);
	int i=1;
	while (i<=n){
		int k=i+1,j=i;
		while (k<=n && s[k]>=s[j]){
			if (s[k]==s[j])
				++j;
			else
				j=i;
			++k;
		}
		while (i<=j){
			q[++cnt]=i+k-j-1;
			i+=k-j;
		}
	}
	int ans=0;
	for (int i=1;i<=cnt;++i)
		ans^=q[i];
	printf("%d
",ans);
	return 0;
}

时间复杂度分析：

首先(i)最多增加(O(n))。考虑最后那个while中(i)要变化成什么，最后一定是(j<ile k)。

转化成这样的问题：有一个队列，有个指针(k)，一开始在位置(1)。每次指针会往后移动一位。你可以在任意时刻，把长度至少(frac{k}{2})的前缀截掉，并将(k)移到剩下的队列的位置(1)。问整个队列都被截掉为止，指针最多会移动多少次。

可以这么想：一开始势能为(n)，截掉一个长度为(l)的前缀增加(l)的势能。于是至多只会移动(2n)次。

oi-wiki上说内层循环次数不超过(4n-3)。它说的循环和我算的大概不是一个东西，但总之就是(O(n))。

进一步思考：

在进行算法时，如果遇到(s_k=s_j)，称其为2情况；如果遇到(s_k>s_j)，称其为3情况；特殊地，如果有一个刚刚重置的(i)，把它视作(k)，称其为1情况。对于一个(k)，如果经历了一次3情况，那么它不会再次经历1情况和2情况和3情况。

解释：遇到3情况时，此时(S_2=w=s[i,k])。(i)不变的时候，这个(k)不可能再被遍历到；(i)如果变了，一定会变到大于等于(k+1)的位置（指这里的(k)而不是那时的(k)）。
(S_2=wwwdots wv)，其中(v)也有可能会由(w'w'w'dots)组成（即存在一个循环前缀）。所以在(i)变化后，需要将(k,j)重置。
Lyndon串的前缀不一定是Lyndon串。设这个Lyndon串为(s)，取前缀(s[1,d])。此时可能存在位置(x)，满足(s[x,d]<s[1,d])，此时一定有(s[x,d])是(s[1,d])的前缀。

（下面例题中的代码中有有关性质的测试）

例题

hdu6761 Minimum Index

题意：给出一个字符串，对于每个前缀求最小后缀的位置。(nle 10^6,sum nle 2*10^7)

上一年多校的时候遇见的，当时rush了一个SAM做法，挂掉了。半年后再看，当时rush的SAM写了好多错误的细节啊……

SAM做法：考虑一个子串(s[l,r])可以贡献到(r)的答案当中。建SAM之后，按照转移边按字典序从小到大遍历SAM（遍历过的节点不再遍历），把这个节点在fail树上的子树打标记。打标记暴力打，如果存在了标记就不打。时间(O(n))，有(26)的小常数。本地跑官方数据大概10s。

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 1000010
#define mo 1000000007
#define ll long long
int n;
char s[N];
struct Node{
    Node *c[26],*fail;
    int len;
} d[N*2],*S,*T;
int cnt;
Node *newnode(){++cnt;memset(&d[cnt],0,sizeof(Node));return &d[cnt];}
void insert(int ch){
    Node *nw=newnode();
    nw->len=T->len+1;
    Node *p=T;
    for (;p && p->c[ch]==0;p=p->fail)
        p->c[ch]=nw;
    if (!p)
        nw->fail=S;
    else{
        Node *q=p->c[ch];
        if (q->len==p->len+1)
            nw->fail=q;
        else{
            Node *clone=newnode();
            memcpy(clone->c,q->c,sizeof q->c);
            clone->fail=q->fail;
            clone->len=p->len+1;
            for (;p && p->c[ch]==q;p=p->fail)
                p->c[ch]=clone;
            nw->fail=q->fail=clone;
        }
    }
    T=nw;
}
int id[N];
struct EDGE{
    int to;
    EDGE *las;
} e[N*2];
int ne;
EDGE *last[N*2];
int fa[N*2];
int cov[N*2];
bool vis[N*2];
void cover(int x,int l){
    if (cov[x])
        return;
    cov[x]=l;
    for (EDGE *ei=last[x];ei;ei=ei->las)
        cover(ei->to,l);
}
void dfs(int x,int s){
    if (vis[x])
        return;
    vis[x]=1;
    if (x!=S-d)
        cover(x,s);
    for (int i=0;i<26;++i)
        if (d[x].c[i])
            dfs(d[x].c[i]-d,s+1);
}
int main(){
	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
    int Q;
    scanf("%d",&Q);
    while (Q--){
        scanf("%s",s+1);
        n=strlen(s+1);
        cnt=0;
        S=T=newnode();
        for (int i=1;i<=n;++i)
            insert(s[i]-'a'),id[i]=T-d;
        ne=0;
        memset(last,0,sizeof(EDGE*)*(cnt+1));
        for (int i=2;i<=cnt;++i){
            fa[i]=d[i].fail-d;
            e[ne]={i,last[fa[i]]};
            last[fa[i]]=e+ne++;
        }
        memset(cov,0,sizeof(int)*(cnt+1));
        memset(vis,0,sizeof(bool)*(cnt+1));
        dfs(S-d,0);
        ll ans=0;
        for (int i=1,pw=1;i<=n;++i,pw=(ll)pw*1112%mo){
            int x=i-cov[id[i]]+1;
            printf("%d ",x);
//            (ans+=(ll)x*pw)%=mo;
        }
//        printf("
");
        printf("%lld
",ans);
    }
    return 0;
}

重新看这题的时候尝试想SA做法，想出个常数比较大的，而且不够优（根据后面对Lyndon分解的分析可以对此进行大幅度优化），所以不讲。

【Lyndon分解做法1】

首先进行Lyndon分解。询问前缀(s[1,d])的最小后缀，首先这个后缀的开头一定在(d)所在Lyndon串（记为(s[h,d])）内。如果有后缀(s[x,d]<s[h,d])，那么一定有(s[x,d])是(s[h,d])的前缀。

考虑对于每个Lyndon串分别处理。对于一个Lyndon串(s[h,t])来说，(s[x,dots])可以贡献的(d)在([x,x+LCP(s[h,t],s[x,t])-1])中。求串中所有后缀和整个串的LCP，这就是exkmp中的(next)数组。跑个exkmp。然后扫一遍，用个单调栈来维护后面哪些区间贡献是多少。

时间(O(n))。然而实测大概和上面SAM做法差不多，10s？

using namespace std;
#include <bits/stdc++.h>
#define N 1000005
#define mo 1000000007
#define ll long long
#define fi first
#define se second
#define mp(x,y) make_pair(x,y)
int n;
char s[N];
int p[N],cnt;
int a[N];
void doit(char s[],int a[],int n,int os){
	static int nxt[N];
	nxt[0]=n;
	int pos=0,mr=0;
	for (int i=1;i<n;++i){
		nxt[i]=(i<mr?min(nxt[i-pos],mr-i):0);
		while (i+nxt[i]<n && s[nxt[i]]==s[i+nxt[i]])
			++nxt[i];
		if (mr<nxt[i])
			mr=nxt[i],pos=i;
	}
	a[0]=0+os;
	static int st[N];
	int tp=1;
	st[1]=0;
	for (int i=1;i<n;++i){
		while (tp && st[tp]+nxt[st[tp]]<i+nxt[i])
			--tp;
		st[++tp]=i;
		while (tp && st[tp]+nxt[st[tp]]<=i)
			--tp;
		a[i]=st[tp]+os;			
	}
}
int main(){
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	int T;
	scanf("%d",&T);
	while (T--){
		scanf("%s",s+1);
		n=strlen(s+1);
		cnt=0;
		int i=1;
		while (i<=n){
			int k=i+1,j=i;
			while (k<=n && s[k]>=s[j]){
				j=(s[k]==s[j]?j+1:i);
				++k;
			}
			while (i<=j){
				p[++cnt]=i;
				i+=k-j;
			}
		}
		p[cnt+1]=n+1;
		for (int i=1;i<=cnt;++i)
			doit(s+p[i],a+p[i],p[i+1]-p[i],p[i]);
		ll ans=0;
		for (int i=1,w=1;i<=n;++i,w=(ll)w*1112%mo)
			(ans+=(ll)a[i]*w)%=mo;
		printf("%lld
",ans);			
	}
	return 0;
}

【Lyndon分解做法2】

如果暴力对(s)的每个前缀做Lyndon分解，那么最后一个Lyndon串显然就是答案。那么有没有增量构造的Lyndon分解算法？

~~至少我想不出来。~~但尽管不是想象中的增量构造，还是有“伪”增量构造方法：

设(a_i)表示前缀(s[1,i])的最小后缀。跑一个普通的Lyndon分解，在算法中加入几句话：

当(i)刚刚被重置时，(a_ileftarrow i)。（记作1情况）

当(s_j=s_k)时，(a_kleftarrow a_j+k-j)。（记作2情况）

当(s_j<s_k)时，(a_kleftarrow i)。（记作3情况）

解释：1情况，(s[1,i])最后一个Lyndon串是(s[i,i])；2情况，因为(S_2=wwwdots wv)，(v)是(w)的前缀，(a_k)应该在(v)中，因为(j)和(k)相当于在(w)中同样的位置，(a_j)也应该在(v)中，两者等价，可以继承；3情况，(s[i,k])成为一个Lyndon串。

时间(O(n))。常数极小，可以通过。

可能存在的问题：

(a_k)不一定是(v)的开头。因为如果单对(v)分解，有可能还是会分成多个Lyndon串，因为Lyndon串的前缀不一定是Lyndon串。
由于(i)重置过后(j,k)都需要被重置，所以某个(a_k)可能会被赋值多次。然而每次赋的值都是一样的。

using namespace std;
#include <bits/stdc++.h>
#define N 1000005
#define mo 1000000007
#define ll long long
int n;
char s[N];
int a[N],b[N],c[N];
int main(){
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	int T;
	scanf("%d",&T);
	while (T--){
		scanf("%s",s+1);
		n=strlen(s+1);
		memset(a,0,sizeof(int)*(n+1));
		memset(b,0,sizeof(int)*(n+1));
		int i=1;
		while (i<=n){
			int k=i+1,j=i;
			if (a[i])
				assert(a[i]==i);
			static int tim;
			if (b[i]==3)
				printf("fuck
");
			a[i]=i,b[k]=1;
			while (k<=n && s[k]>=s[j]){
				if (s[k]==s[j]){
					if (a[k])
						assert(a[k]==a[j]+k-j);
					if (b[k]==3)
						printf("fuck
");
					a[k]=a[j]+k-j,b[k]=2;
					++j,++k;
				}
				else{
					if (a[k])
						assert(a[k]==i);
					++tim;
					if (b[k]==3)
						printf("fuck
");
					a[k]=i,b[k]=3;
					j=i,++k;
				}
			}
			i=k-(j-i)%(k-j); 
//			while (i<=j)
//				i+=k-j;
		}
		ll ans=0;
		for (int i=1,w=1;i<=n;++i,w=(ll)w*1112%mo)
			(ans+=(ll)a[i]*w)%=mo;
		printf("%lld
",ans);			
	}
	return 0;
}