本篇博客还未完成。后续还有一点内容。
一些记号约定
- \(s[i,j]\) 表示字符串 \(s\) 截取下标在 \(i,j\) 中的字符得到的子串。
- \(s+t\) 表示两个字符（串）\(s,t\) 连接的结果。
- \(s^g\) 表示将 \(s\) 重复 \(g\) 遍的结果。
- \(s^r\) 表示 \(s\) 的反串。
- 下文若无特殊说明，字符串下标从 \(1\) 开始。
最小表示法
对于字符串 \(s\) 的所有循环同构串，称字典序最小的一个为 \(s\) 的最小表示。
下面我们来求长度为 \(n\) 的字符串 \(s\) 的最小表示。只需求出最小表示的开始下标即可（此处字符串从 \(0\) 开始编号）。
我们设置 \(2\) 个指针 \(i=0,j=1\)，表示两个候选开始下标。再设置一个 \(k\)，为使得 \(s[i,i+k]=s[j,j+k]\) 的最大的 \(k\)。我们尝试增大 \(k\) 直到不匹配。考虑两种情况：
- \(s_{i+k}>s_{j+k}\)，则 \(\forall x\in [0,k],s[i+x,i+x+n-1]>s[j+x,j+x+n-1]\)。所以开始下标在 \([i,i+k]\) 这个区间一定没有 \(j\) 优。令 \(i\leftarrow i+k+1\)。
- \(s_{i+k}<s_{j+k}\)，同理 \(j\leftarrow j+k+1\)。
存在一个优化：移动 \(i\) 时可以令 \(i\leftarrow \max(i+k+1,j+1)\)，因为 \([i,j-1]\) 一定不优，否则 \(j\) 不会跳过这一段。\(j\) 移动时同理。
最后取 \(\min(i,j)\) 保证合法即为答案。
时间复杂度 \(O(n)\)。
下面的代码可以通过模板题 P1368 【模板】最小表示法。
#include<bits/stdc++.h>
using namespace std;
const int N=300010;
int a[N];
int main(){
int n,x=0,y=1,k=0,ans;
scanf("%d",&n);
for(int i=0;i<=n-1;i++){
scanf("%d",&a[i]);
}
while(x<=n-1&&y<=n-1&&k<=n-1){
if(a[(x+k)%n]==a[(y+k)%n]){
k++;
}
else{
if(a[(x+k)%n]>a[(y+k)%n]){
x=max(x+k+1,y+1);
}
else{
y=max(y+k+1,x+1);
}
k=0;
}
}
ans=min(x,y);
for(int i=0;i<=n-1;i++){
printf("%d ",a[(ans+i)%n]);
}
}
下面有几个板子：
Lyndon 分解
定义
对于字符串 \(s\)，如果 \(s\) 的字典序严格小于 \(s\) 的所有后缀的字典序，我们称 \(s\) 是 Lyndon 串。
对于字符串 \(s\)，将其分解为 \(m\) 个连续子串 \(s_1+s_2+\cdots+s_m=s\)，若 \(s_i\) 均为 Lyndon 串且 \(s_i\ge s_{i+1}(i\ne m)\)，则称这种分解为 \(s\) 的 Lyndon 分解。
对于字符串 \(s\)，如果它可以分解为 \(w^k+t\) 的形式，其中 \(w\) 为 Lyndon 串，\(t\) 为 \(w\) 的前缀，则称 \(s\) 为近似 Lyndon 串。
性质
性质 1：对于两个 Lyndon 串 \(u,v(u<v)\)，\(u+v\) 也是一个 Lyndon 串。
性质 1 证明：\(u+v\) 的最小表示只能为 \(u+v\) 或 \(v+u\)，因为 \(u<v\)，所以 \(u+v\) 必然是 Lyndon 串。
性质 2：每个字符串都有 Lyndon 分解。
性质 2 证明：我们先将 \(s\) 中每个字符视为一个 Lyndon 串，则可以使用性质一进行合并，直到满足 Lyndon 分解的条件。得证。
性质 3：每个字符串的 Lyndon 分解是唯一的。
性质 3 证明：设字符串 \(s\) 有两个 Lyndon 分解 \(s_1+s_2+\cdots+s_{i-1}+s_i+s_{i+1}+\cdots+s_m\) 和 \(s_1+s_2+\cdots+s_{i-1}+s_i'+s_{i+1}'+\cdots+s_k'\)。设 \(s_i=s_i'+s_{i+1}'+\cdots+s_j'[1,l]\)，则 \(s_i>s_i'\ge s_{i+1}'\ge\cdots\ge s_j'[1,l]\)。因为 \(s_i\) 是 Lyndon 串，所以 \(s_j'[1,l]>s_i\)，推出 \(s_i>s_i\)，矛盾，原命题得证。
性质 4：现有长度为 \(n-1\) 的字符串 \(s\) 和字符 \(c,d(c<d)\)，若字符串 \(s+c\) 为 Lyndon 串的前缀，则 \(s+d\) 为 Lyndon 串。
性质 4 证明：因为 \(s+c\) 为 Lyndon 串的前缀，则:
\[\begin{aligned} &(s+d)[i,n]>(s+c)[i,n]>(s+c)[1,n-i+1](i>1)\\ \Rightarrow&(s+d)[i,n]>(s+c)[1,n-i+1]+(s+d)[n-i+2,n](i>1)\\ \Rightarrow&(s+d)[i,n]>(s+d)(i>1) \end{aligned} \]得证。
性质 5：Lyndon 串没有 border。
性质 5 证明：如果存在 border，那么 border 就是最小后缀，这个串就不是 Lyndon 串。
求解
我们使用 Duval 算法求出一个字符串 \(s\) 的 Lyndon 分解。算法过程进行中将 \(s\) 分为 \(s_1+s_2+s_3\) 三个部分，\(s_1\) 是已经分解完的串，\(s_2=w^k+t\) 是一个近似 Lyndon 串，\(s_3\) 是未处理的部分。取 \(3\) 个指针 \(i,j,k\)。\(i\) 指向 \(s_2\) 的开头，\(k\) 指向 \(s_3\) 的开头，即要加进来的字符，\(j\) 指向 \(k-|w|\)，即 \(k\) 对应的上一次出现的位置。分类讨论：
- \(s_j=s_k\)，不会改变近似 Lyndon 串的性质，\(j\leftarrow j+1,k\leftarrow k+1\)。
- \(s_j<s_k\)，通过性质 3 可以得出 \(t+s_k\) 为 Lyndon 串。并且 \(w<w^f+t+s_k(f\ge 0)\)。因此根据性质 1，我们可以一直向前合并，把 \(s[i,k]\) 作为一个新的 Lyndon 串。即 \(j\leftarrow i,k\leftarrow k+1\)。
- \(s_j>s_k\)，再往后不可能形成新的 Lyndon 串。一直令 \(i\leftarrow i+|w|=i+k-j\)，把前面的循环的 \(w\) 都拎出来。
时间复杂度 \(O(n)\)。
下面的代码可以通过模板题 P6114 【模板】Lyndon 分解。
#include<bits/stdc++.h>
using namespace std;
const int N=5000010;
char a[N];
int main(){
int n,x=1,y,z,ans=0;
scanf("%s",a+1);
n=strlen(a+1);
while(x<=n){
y=x;
z=x+1;
while(a[y]<=a[z]&&z<=n){
if(a[y]==a[z]){
y++;
z++;
}
else{
y=x;
z++;
}
}
while(x<=y){
x+=(z-y);
ans^=x-1;
}
}
printf("%d",ans);
}
Lyndon 分解与最小表示法
我们将长为 \(n\) 的字符串 \(s\) 复制一遍变成 \(s+s\)，对其做 Lyndon 分解，其中 Lyndon 分解中下标最大且 \(\leq n\) 的 Lyndon 串起点就是最小表示的起点。
例题
先来一个小练习。
CF100162G Lyndon Words
给出 \(n,m,l,r\)，按字典序输出长度不超过 \(n\)，字符集为前 \(m\) 个小写字母，按字典序排序后序号在 \([l,r]\) 之间的所有字符串。
\(n\leq 30,m\leq 26,1\leq l\leq r\leq 10^7\)。
考虑直接搜索。按照 Duval 算法的流程，记录 \(j,k\) 即可。枚举 \(s_k\)，如果 \(s_j\leq s_k\) 即可往后继续搜。考虑这个过程生成的冗余串，他们都是以某一个 Lyndon 串作为周期的近似 Lyndon 串。我们发现生成一个长为 \(k\) 的 Lyndon 串需要的复杂度为 \(O(k)\)，它会接着生成 \(n-k\) 个冗余串，加起来 \(O(n)\)。因此总时间复杂度为 \(O(nr)\)。
#include<bits/stdc++.h>
using namespace std;
int n,m,l,r,now;
char s[50];
void dfs(int y,int z){
if(y==1){
now++;
if(now>=l&&now<=r){
printf("%s\n",s+1);
}
if(now==r){
return;
}
}
if(z>n){
return;
}
for(int i=1;i<=m&&now<r;i++){
s[z]='a'+i-1;
if(s[y]==s[z]){
dfs(y+1,z+1);
}
else if(s[y]<s[z]){
dfs(1,z+1);
}
}
s[z]=0;
}
int main(){
int cnt=0;
while(scanf("%d%d%d%d",&n,&m,&l,&r)!=EOF){
now=0;
printf("Case %d:\n",++cnt);
for(int i=1;i<=m&&now<r;i++){
s[1]='a'+i-1;
dfs(1,2);
}
}
}
P5334 [JSOI2019] 节日庆典
给出长为 \(n(n\leq 3\times 10^6)\) 的字符串 \(s\)，求 \(s\) 的每个前缀的最小表示法的开始下标。有多个选最小的。
考虑魔改 Duval 算法。还是有三个指针 \(i,j,k\)，还是分类讨论：
-
\(s_j<s_k\)，\(s[i,k]\) 形成一个新的 Lyndon 串。\(ans_k\leftarrow i\)。
-
\(s_j>s_k\)，把前面的 Lyndon 串拎出来，后面的一段答案还不能确定。
-
\(s_j=s_k\)，串为 \(s=w^k+t\)。考虑答案可能是什么样的。一是 \(i\)。二是下标在 \(t\) 中。对于后者，我们考虑出来的最小表示法最后一定有循环节，去掉一个就是 \(j\) 的最小表示法，所以为 \(ans_j+k-j\)（当然，需要 \(ans_j\ge i\)）。我们比较这两个的大小。即比较 \(s[i,k]+s[1,i-1]\) 与 \(s[ans_j+k-j,k]+s[1,ans_j+k-j-1]\)。注意到 \(ans_j\) 一定是 \(i\) 加上若干个 Lyndon 串的周期得到的，所以 \(s[i,i+k-(ans_j+k-j)]=s[ans_j+k-j,k]\)。然后我们就只要比较 \(s[i+k-(ans_j+k-j)+1,k]+s[1,i-1]\) 与 \(s[1,ans_j+k-j-1]\)。分成 \(2\) 段比较，注意到两段都是一个前缀和一个子串比较，使用 exKMP 预处理出 \(z\) 数组即可。
时间复杂度 \(O(n)\)。
#include<bits/stdc++.h>
using namespace std;
const int N=3000010;
int z[N],ans[N];
char s[N];
void init(int n){
int l=0,r=0;
for(int i=2;i<=n;i++){
if(i<r){
z[i]=min(r-i+1,z[i-l+1]);
}
while(i+z[i]<=n&&s[z[i]+1]==s[i+z[i]]){
z[i]++;
}
if(i+z[i]-1>r){
l=i;
r=i+z[i]-1;
}
}
}
int getmin(int i,int j,int k,int ans){
int x=i+k-(ans+k-j)+1;
if(z[x]<k-x+1){
return s[x+z[x]]<s[z[x]+1]?i:ans+k-j;
}
x=k-x+2;
if(z[x]<i-1){
return s[x+z[x]]<s[z[x]+1]?ans+k-j:i;
}
else{
return i;
}
}
int main(){
int n,x=1,y,z;
scanf("%s",s+1);
n=strlen(s+1);
init(n);
while(x<=n){
if(!ans[x]){
ans[x]=x; //此处应为 Lyndon 串开头。
}
y=x;
z=x+1;
while(s[y]<=s[z]){
if(s[y]==s[z]){
if(!ans[z]){
if(ans[y]>=x){
ans[z]=getmin(x,y,z,ans[y]);
}
else{
ans[z]=x;
}
}
y++;
z++;
}
else{
y=x;
if(!ans[z]){
ans[z]=x;
}
z++;
}
}
while(x<=y){
x+=(z-y);
}
}
for(int i=1;i<=n;i++){
printf("%d ",ans[i]);
}
}
P9719 [EC Final 2022] Minimum Suffix
对于长度为 \(n\) 的字符串 \(s\)，如果 \(s[x,i]\) 是 \(s[1,i]\) 的最小后缀，则我们定义 \(p_i=x\)。
你需要从 \(p_1,\ldots, p_n\) 中恢复出 \(s\)。如果存在多个答案，找出字典序最小的那个。
\(n\leq 3\times 10^6\)。
考虑我们能从 \(p_i\) 中得到什么信息。显然 \(s[p_i,i]\) 为 Lyndon 串，且 \(\forall j<p_i,s[j,i]\) 不是 Lyndon 串。从 \(p_n\) 开始往前，可以得到 \(s[p_n,n]\) 为最后一个 Lyndon 串，\(s[p_{p_n-1},p_n-1]\) 为倒数第二个。以此类推可以求出原串的 Lyndon 分解。
考虑模拟 Duval 算法。我们对于每一个 Lyndon 串 \(s[l,r]\) 模拟即可。只需维护 \(j\) 和 \(k\)。还是分类讨论。
-
\(s_j=s_k\)，判断方法为 \(j-p_j=k-p_k\)。
-
\(s_j<s_k\)，形成了新的 Lyndon 串。判断方法为 \(p_j=l\)。
-
\(s_j>s_j\)，因为我们最先已经分出了 Lyndon 串，这种情况不会出现，如果不是前面 \(2\) 种情况即无解。
于是我们可以对于每个 \(k\) 求出 \(pre_k=j\) 和 \(s_{pre_k}\) 与 \(s_k\) 的大小关系。记这个为 \(val_k\)，\(s_j=s_k\) 则为 \(0\)，否则为 \(1\)。
构造考虑贪心。对于同一个 Lyndon 串，从前往后考虑。若 \(val_i\) 为 \(0\) 则直接复制 \(s_{pre_i}\)，否则 \(+1\)。
当有多个 Lyndon 串时，因为前面的不小于后面的，因此从后往前贪心。记后一个 Lyndon 串为 \(last\)，如果发现 \(s_i\) 对应位置比 \(last\) 小，使得 \(s<last\)，此时还是分类：
-
\(val_i=1\)，直接 \(+1\) 即可。
-
\(val_i=0\)，与前面的有相同关系，因此需把前一个 \(val_j=1\) 的 \(s_j\) 加上 \(1\)。然后从 \(j+1\) 重新开始贪心。此时发现 \(s\) 已经大于 \(last\)，因此这种调整最多只会进行一次。
如果最后 \(s\) 是 \(last\) 的前缀，也进行一次第二种调整。
时间复杂度 \(O(n)\)。
#include<bits/stdc++.h>
using namespace std;
const int N=3000010;
int m,a[N],last[N],pre[N],p[N],val[N],s[N];
int las(int x){
if(x>m){
return 0;
}
return last[x];
}
int main(){
int t,n,l,r,len,gt,now;
scanf("%d",&t);
while(t--){
m=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&p[i]);
}
r=n;
while(r>=1){
l=p[r];
val[l]=1;
for(int i=l;i<=r;i++){
if(p[i]<l){
printf("-1\n");
goto lass;
}
}
len=1;
for(int i=l+1;i<=r;i++){
pre[i]=i-len;
if(p[i]==l){
val[i]=1;
len=i-l+1;
}
else if(i-p[i]==i-len-p[i-len]){
val[i]=0;
}
else{
printf("-1\n");
goto lass;
}
}
gt=0; //是否大于
s[l]=las(1);
for(int i=l+1;i<=r;i++){
s[i]=s[pre[i]]+val[i];
if(s[i]>las(i-l+1)){
gt=1;
}
if(!gt&&s[i]<las(i-l+1)){
if(val[i]){
s[i]=las(i-l+1);
}
else{
now=i;
while(val[now]!=1){
now--;
}
i=now;
s[i]++;
gt=1;
}
}
}
if(!gt&&r-l+1<m){
now=r;
while(val[now]!=1){
now--;
}
s[now]++;
for(int i=now+1;i<=r;i++){
s[i]=s[pre[i]]+val[i];
}
}
m=r-l+1;
for(int i=l;i<=r;i++){
last[i-l+1]=s[i];
}
r=l-1;
}
for(int i=1;i<=n;i++){
printf("%d ",s[i]+1);
}
printf("\n");
lass:;
}
}
CF594E Cutting the Line
给定长为 \(n\) 的字符串 \(s\) 和一个正整数 \(k\)。你可以将 \(s\) 分成至多 \(k\) 段，并将每一段翻转或者不翻转。求最终能够得到的字典序最小的 \(s\)。\(n\leq 5\times 10^6\)。
大分讨警告。
下文记 \(w=s^r\)。
若 \(k=1\)，答案只能为 \(s\) 或 \(w\)，比较输出即可。
否则我们先考虑 \(k=n\)。
注意到我们可以得到一种方案，使得每个被划分出来的子串都被翻转过。把答案串中未翻转的子串视为单个字符即可。题意转化为：每次取 \(w\) 的一个后缀接到答案串最后。将 \(w\) Lyndon 分解，每次取最后的一个 Lyndon 串即可。
考虑 \(k<n\)。我们需要尽量减少划分次数。有两个结论：
- 若划分出的串相邻且相同，则可以把它们合并。
- 若划分出的串相邻且均为回文串，则可以把他们合并，最后拿出来的时候翻转，相当于在 \(s\) 中不翻转。
考虑一个引理：一个 Lyndon 串为回文串当且仅当它只包含 \(1\) 个字符。
证明：考虑 Lyndon 串性质 5，若长度大于 \(1\)，第一个字符与最后一个一定是一对 border，得证。
当 \(k\ge 3\)，我们可以直接贪心。设当前 Lyndon 串为 \(t\)，在结尾出现了 \(f\) 次，按照以下步骤进行：
-
若 \(|t|>1\)，则将 \(f\) 个串直接拿出来，\(k\) 减去 \(1\)。
-
否则，若前面一种 Lyndon 串的长度 \(\ne 1\)，同样将 \(f\) 个串拿出来，\(k\) 减去 \(1\)。
-
否则，可以将这种串与前面的合并，\(k\) 不变。
最后来考虑 \(k=2\)。我们可以枚举在原串 \(s\) 中的分界点，然后 SAM 查询。但是比较臭。我们考虑继续分讨。
相当于要把现在的 \(w\) 分成 \(t_2+t_1\)，最后的答案为 \(t_1^{(r)}+t_2^{(r)}\)。依次讨论：
\(t_1^r+t_2^r\)，相当于 \(w^r\)。
\(t_1+t_2\)，相当于求最小表示。
\(t_1^r+t_2\)，我们从小到大枚举 \(t_1\) 的起点，设现在的最优答案为 \(i\)，枚举到 \(j\)。我们需要比较 \(w[i,n]^r+w[1,i-1]\) 与 \(w[j,n]^r+w[1,j-1]\) 的大小关系。消去重复部分即为 \(w[i,j-1]^r+w[1,i-1]\) 与 \(w[1,j-1]\)。考虑和P5334 [JSOI2019] 节日庆典一样的方法 exKMP 即可。
\(t_1+t_2^r\)，我们挖掘一点性质。
记 \(w\) 的 Lyndon 分解为 \(a_1^{c_1}+a_2^{c_2}+\cdots+a_m^{c_m}\)。其中 \(a_1>a_2>\cdots>a_m\)。记 \(b_i=a_i^{c_i},B_i=b_i+b_{i+1}+\cdots+b_m\)。我们可以发现 \(t_1\) 为某个 \(B_i\)。证明显然。易得 \(B_i>B_{i+1}\)。考虑若 \(t_1=B_i\)，则 \(B_{i+1}\) 一定为 \(B_i\) 的前缀，否则 \(B_{i+1}\) 一定最优。我们先找到最大的一个 \(p\) 使得 \(B_p\) 不是 \(B_{p-1}\) 的前缀。我们还有一个结论：若 \(t_1=B_i\) 优于 \(t_1=B_{i-1}\)，则它也优于 \(t_1=B_{i-2}\)。证明：设 \(B_i,B_{i-1},B_{i-2}\) 的开始下标为 \(x,y,z\)。条件相当于 \(w[x,n]+w[y,x-1]^r+w[1,y-1]^r>w[y,y+|B_i|]+w[y+|B_i|+1,n]+w[1,y-1]^r\)，即 \(w[x,n]+w[y,x-1]^r>w[y,y+|B_i|-1]+w[y+|B_i|,n]=B_{i-1}=w[z,z+|B_{i-1}|-1]\)。得证。
因此，我们找到最大的一个 \(q(q>p)\) 使得 \(t_1=B_q\) 优于 \(t_1=B_{q-1}\) 即为答案。若找不到，答案即为 \(p\)。
暴力比较一次 \(t_1=B_i\) 和 \(t_1=B_{i-1}\) 的时间复杂度为 \(O(|B_{i-1}|)\)，总时间复杂度为 \(\sum\limits_{i=p}^{m-1}|B_i|\)。注意到由于有前缀关系，可以发现 \(|b_i|\ge|B_{i+1}|\)，即 \(|B_i|\ge2|B_{i+1}|\)。因此求和还是 \(O(|B_p|)\) 的。
总时间复杂度 \(O(n)\)。
#include<bits/stdc++.h>
using namespace std;
const int N=5000010;
int n,cnt,z[N<<1];
char s[N],w[N],ans[N],tmp[N],q[N<<1];
struct ss{
int l,r,len;
}p[N];
bool check1(char *a,char *b){
for(int i=1;i<=n;i++){
if(a[i]<b[i]){
return 0;
}
else if(a[i]>b[i]){
return 1;
}
}
return 0;
}
void Lyndon(){
int x=1,y,z;
while(x<=n){
y=x;
z=x+1;
while(w[y]<=w[z]){
if(w[y]==w[z]){
y++;
z++;
}
else{
y=x;
z++;
}
}
p[++cnt]={x,0,z-y};
while(x<=y){
x+=(z-y);
}
p[cnt].r=x-1;
}
}
void upd(char *now){
for(int i=1;i<=n;i++){
if(now[i]<ans[i]){
for(int j=1;j<=n;j++){
ans[j]=now[j];
}
return;
}
else if(now[i]>ans[i]){
return;
}
}
}
void get_min(char *minn){
int x=1,y=2,k=0,st;
while(x<=n&&y<=n&&k<=n-1){
if(w[(x+k-1)%n+1]==w[(y+k-1)%n+1]){
k++;
}
else{
if(w[(x+k-1)%n+1]>w[(y+k-1)%n+1]){
x=max(x+k+1,y+1);
}
else{
y=max(y+k+1,x+1);
}
k=0;
}
}
st=min(x,y);
for(int i=0;i<=n-1;i++){
minn[i+1]=w[(st+i-1)%n+1];
}
}
void exkmp(){
int l=0,r=0;
for(int i=1;i<=n;i++){
q[i]=w[i];
}
for(int i=n+1;i<=n*2;i++){
q[i]=w[n-(i-n)+1];
}
for(int i=2;i<=n*2;i++){
if(r>i){
z[i]=min(r-i+1,z[i-l+1]);
}
while(i+z[i]<=n*2&&q[z[i]+1]==q[i+z[i]]){
z[i]++;
}
if(i+z[i]-1>r){
l=i;
r=i+z[i]-1;
}
}
}
bool cmp(int i,int j){
int x=n+(n-(j-1))+1;
if(z[x]<(j-1)-i+1){
return w[z[x]+1]<w[j-1-z[x]]?1:0;
}
x=(j-1)-i+2;
if(z[x]<i-1){
return w[z[x]+1]<w[x+z[x]]?0:1;
}
else{
return 0;
}
}
void get_kmp(char *minn){
int now=1,cnt=0;
for(int i=2;i<=n;i++){
if(cmp(now,i)){
now=i;
}
}
for(int i=n;i>=now;i--){
minn[++cnt]=w[i];
}
for(int i=1;i<=now-1;i++){
minn[++cnt]=w[i];
}
}
void get_min2(char *minn){
int now=cnt,fl=1,ans;
while(now>1){
for(int i=p[now].l,j=p[now-1].l;i<=p[now].r;i++,j++){
if(w[i]<w[j]){
fl=0;
}
}
if(!fl){
break;
}
now--;
}
ans=now;
while(now<cnt){
now++;
for(int i=p[now].l-1,j=p[now-1].l+p[now].len;j<=n;i--,j++){
if(w[i]<w[j]){
ans=now;
break;
}
else if(w[i]>w[j]){
break;
}
}
}
ans=p[ans].l;
now=0;
for(int i=ans;i<=n;i++){
minn[++now]=w[i];
}
for(int i=ans-1;i>=1;i--){
minn[++now]=w[i];
}
}
int main(){
int k;
scanf("%s%d",s+1,&k);
n=strlen(s+1);
for(int i=1;i<=n;i++){
w[i]=s[n-i+1];
}
if(k==1){
printf("%s",check1(s,w)==0?(s+1):(w+1));
return 0;
}
Lyndon();
while(cnt&&k>=3){
for(int i=p[cnt].l;i<=p[cnt].r;i++){
printf("%c",w[i]);
}
if(p[cnt].len!=1){
k--;
}
else{
if(p[cnt-1].len!=1){
k--;
}
}
cnt--;
}
if(!cnt){
return 0;
}
n=p[cnt].r;
for(int i=1;i<=n;i++){
ans[i]=w[n-i+1];
}
get_min(tmp);
upd(tmp);
exkmp();
get_kmp(tmp);
upd(tmp);
get_min2(tmp);
upd(tmp);
printf("%s",ans+1);
}
Yandex.Algorithm.2015 Round 2.2 F Lexicographically Smallest String
给你一个字符串 \(s\)，你可以选择任意一个区间进行翻转，使操作后的字符串字典序最小。\(|s|\leq 10^7\)。
显然最后字符串的开始字符一定是字符串内最小的。删去已经合法的前缀，转化为需要翻转一个前缀，即上一道题最后一种情况。代码不放了。
QOJ #243 Lyndon Substring / HDU 6306 Lyndon Substring
给出 \(n\) 个字符串 \(s_{1\sim n}\)，再给出 \(m\) 个询问 \(x,y\)，求 \(s_x+s_y\) 的最长 Lyndon 子串的长度。
\(n,m\leq 10^5,|s_i|\leq 10^5,\sum|s_i|\leq 5\times 10^5\)。
考虑先把 \(n\) 个串 Lyndon 分解。\(s_x+s_y\) 的答案一定为 \(s_x,s_y\) 的最大值和中间形成的 Lyndon 串的最大值。考虑后者怎么求。对于每一个串 \(s_i\)，设它的 Lyndon 分解为 \(a_1^{d_1}+a_2^{d_2}+\cdots+a_k^{d_k}=b_1+b_2+\cdots+b_k\)。设 \(B_i=b_i+b_{i+1}+\cdots+b_k\)，我们在 Duval 算法过程中求出所有 \(B_i\) 中的近似 Lyndon 串，设为 \(las_i\)。显然只有这些串可能可以和后面的字符接起来形成最优解，即存在一个 \(f\) 满足 \((s_x+s_y)[las_i,las_i+f-1]=(s_x+s_y)[las_{i+1},las_{i+1}+f-1]\) 且 \((s_x+s_y)_{las_i+f}<(s_x+s_y)_{las_{i+1}+f}\)，此时 \((s_x+s_y)[las_i,las_{i+1}+f]\) 为一个大 Lyndon 串。显然我们选 \(las_i\) 最小的一个是符合 Duval 算法的过程的。
确定了左端点，我们来考虑确定右端点。我们只需在 \(s_y\) 的所有 Lyndon 串中二分出最后一个可以与前面合并的串即可。正确性显然。
对于字符串 \(s\)，易得所有 \(las\) 都有前缀关系。因此 \(las\) 大小不超过 \(\log|s|\)。时间复杂度 \(O(\sum|s_i|+m\log^2|s_i|)\)。
代码中字符串下标从 \(0\) 开始。
#include<bits/stdc++.h>
using namespace std;
const int N=100010,base=41,mod=1e9+9;
string s[N];
int maxx[N],pw[N];
vector<int>las[N];
vector<pair<int,int> >lyndon[N];
struct hs{
vector<int>p;
void set(string& s){
int n=s.length();
p.resize(n);
p[0]=s[0];
for(int i=1;i<=n-1;i++){
p[i]=(1ll*p[i-1]*base+s[i])%mod;
}
}
int get(int l,int r){
if(l==0){
return p[r];
}
return (p[r]-1ll*p[l-1]*pw[r-l+1]%mod+mod)%mod;
}
}p[N];
void Lyndon(int i,string& s){
int n=s.length(),x=0,y,z;
maxx[i]=0;
las[i].clear();
lyndon[i].clear();
while(x<=n-1){
y=x;
z=x+1;
while(s[y]<=s[z]){
if(s[y]==s[z]){
y++;
z++;
}
else{
y=x;
z++;
}
}
if(z==n){
las[i].push_back(x);
}
while(x<=y){
lyndon[i].push_back({x,x+z-y-1});
x+=(z-y);
}
maxx[i]=max(maxx[i],z-y);
}
las[i].push_back(n);
}
int calc(int x,int y,int a,int len){
if(a+len-1<s[x].length()){
return p[x].get(a,a+len-1);
}
if(a>=s[x].length()){
return p[y].get(a-s[x].length(),a-s[x].length()+len-1);
}
return (1ll*p[x].get(a,s[x].length()-1)*pw[a+len-s[x].length()]%mod+p[y].get(0,a-s[x].length()+len-1))%mod;
}
char get(int x,int y,int a){
if(a<s[x].length()){
return s[x][a];
}
return s[y][a-s[x].length()];
}
bool check(int x,int y,int a,int b,int len){
int l=1,r=len,mid,ans=0;
if(calc(x,y,a,len)==calc(x,y,b,len)){
return 0;
}
while(l<=r){
mid=(l+r)>>1;
if(calc(x,y,a,mid)==calc(x,y,b,mid)){
l=mid+1;
ans=mid;
}
else{
r=mid-1;
}
}
return get(x,y,a+ans)<get(x,y,b+ans);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t,n,m,x,y,a,b,now,ans,l,r,mid,anss;
cin>>t;
pw[0]=1;
for(int i=1;i<=100000;i++){
pw[i]=1ll*pw[i-1]*base%mod;
}
while(t--){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s[i];
Lyndon(i,s[i]);
p[i].set(s[i]);
}
while(m--){
cin>>x>>y;
now=-1;
ans=max(maxx[x],maxx[y]);
for(int i=0;i<las[x].size()-1;i++){
a=las[x][i];
b=las[x][i+1];
if(check(x,y,a,b,s[x].length()-b+s[y].length())){
now=a;
break;
}
}
if(now!=-1){
l=0;
r=lyndon[y].size()-1;
while(l<=r){
mid=(l+r)>>1;
if(check(x,y,now,s[x].length()+lyndon[y][mid].first,lyndon[y][mid].second-lyndon[y][mid].first+1)){
l=mid+1;
anss=lyndon[y][mid].second+1;
}
else{
r=mid-1;
}
}
ans=max(ans,(int)s[x].length()-now+anss);
}
cout<<ans<<"\n";
}
}
}
事实上，这里的 \(las\) 就是下面的 Significant Suffixes。
Significant Suffixes
定义
一个字符串 \(s\) 的 Significant Suffixes 是一个后缀的集合，满足对于每个元素 \(w\)，都存在一个字符串 \(t\)（可以为空），使得 \(w\) 是 \(s+t\) 的最小后缀。
性质
性质 1：对于 \(s\) 的任意两个 Significant Suffixes \(u,v(|u|<|v|)\)，满足 \(u\) 是 \(v\) 的前缀。
性质 1 证明：若条件不成立，\(s\) 之后加上任意字符串，\(u,v\) 后缀的大小关系显然不变，不可能同时为 Significant Suffixes。
注意到此时 \(u\) 其实是 \(v\) 的 border。
性质 2：对于 \(s\) 的任意两个 Significant Suffixes \(u,v(|u|<|v|)\)，有：\(2|u|\leq|v|\)。
性质 2 证明：若存在 \(u,v\) 使得 \(|u|<|v|<2|u|\)，根据前面的 border 结论，\(v\) 有长为 \(|v|-|u|\) 的周期。设为 \(w\)，则 \(u\) 应为 \(w^k+r\)，\(v\) 为 \(w^{k+1}+r\)，其中 \(r\) 为 \(w\) 的前缀，\(k\ge 1\)。我们现在知道存在一个 \(t\) 使得 \(u+t<v+t\)，即 \(w^k+r+t<w^{k+1}+r+t\)。即 \(w^{k-1}+r+t<w^k+r+t=u+t\)，所以 \(u\) 必然不是 Significant Suffix。得证。
性质 2 推论：串 \(s\) 的 Significant Suffixes 集合大小不超过 \(\log|s|\)。
例题
P5211 [ZJOI2017] 字符串
维护一个动态字符串 \(s\)，字符集为整数。有 \(m\) 个操作。操作有两种：
-
输入 \(l, r, d\)，对于所有 \(l \leq i \leq r\)，将 \(s_i\) 修改为 \(s_i + d\)。
-
输入 \(l, r\)，输出子串 \(s[l,r]\) 的字典序最小的后缀的起点位置。
\(n\leq 2\times 10^5,m\leq 3 \times 10^4,|d|\leq 10^3,|s_i|\leq 10^8\)。
DS 警告。
我们考虑使用线段树维护这个字符串的 Significant Suffixes。考虑线段树上一个节点的两个子节点 \(p_1,p_2\) 满足 \(len_1=len_2\) 或 \(len_1=len_2+1\)。合并时先把 \(p_2\) 的 Significant Suffixes 继承过来，根据性质 2，\(p_1\) 最多只会贡献一个 Significant Suffix。显然我们在 \(p_1\) 的 Significant Suffixes 中取字符串最小的一个即可（即使这一个不合法也算进去，反正不会影响答案或时间复杂度）。统计答案时在线段树 \(O(\log n)\) 个节点中统计最小的即可。这一部分的时间复杂度为 \(O(m\log^2 n)\) 再乘上询问字符串大小关系的复杂度。注意一些细节：在合并两个节点的时候，如果两个字符串有前缀关系，要取下标小的那一个。证明类似性质 2 证明。而统计答案时要取下标大的那一个。
查询字符串大小关系时，因为带修，并且查询次数多，考虑分 \(\sqrt n\) 块维护哈希。维护块内前缀哈希和从开始到这一块结束的哈希值即可。查询时二分答案 + \(O(1)\) 回答哈希值。总时间复杂度 \(O(n\log^2 n+m\log^3 n+m\sqrt n)\)。
#include<bits/stdc++.h>
using namespace std;
const int N=200010,M=450,base=41,mod=1e9+9,maxx=2e8;
int n,a[N],ans;
vector<int>v[N<<2];
struct Block{
int blo,cnt,bel[N],L[M],R[M],pw[N],p[N],q[N],del[M],sumpw[N];
void init(){
blo=sqrt(n);
cnt=ceil(1.0*n/blo);
pw[0]=sumpw[0]=1;
for(int i=1;i<=n;i++){
pw[i]=1ll*pw[i-1]*base%mod;
sumpw[i]=(sumpw[i-1]+pw[i])%mod;
}
for(int i=1;i<=cnt;i++){
L[i]=(i-1)*blo+1;
R[i]=min(i*blo,n);
p[L[i]]=a[L[i]];
bel[L[i]]=i;
for(int j=L[i]+1;j<=R[i];j++){
p[j]=(1ll*p[j-1]*base+a[j])%mod;
bel[j]=i;
}
}
for(int i=1;i<=cnt;i++){
q[i]=(1ll*q[i-1]*pw[R[i]-L[i]+1]+p[R[i]])%mod;
}
}
void update(int x,int y,int z){
int ql=bel[x],qr=bel[y];
if(ql==qr){
for(int i=x;i<=y;i++){
a[i]+=z;
}
p[L[ql]]=a[L[ql]];
for(int i=L[ql]+1;i<=R[ql];i++){
p[i]=(1ll*p[i-1]*base+a[i])%mod;
}
for(int i=ql;i<=cnt;i++){
q[i]=(1ll*q[i-1]*pw[R[i]-L[i]+1]+(p[R[i]]+1ll*sumpw[R[i]-L[i]]*del[i])%mod)%mod;
}
return;
}
for(int i=x;i<=R[ql];i++){
a[i]+=z;
}
p[L[ql]]=a[L[ql]];
for(int i=L[ql]+1;i<=R[ql];i++){
p[i]=(1ll*p[i-1]*base+a[i])%mod;
}
for(int i=ql+1;i<=qr-1;i++){
del[i]+=z;
}
for(int i=L[qr];i<=y;i++){
a[i]+=z;
}
p[L[qr]]=a[L[qr]];
for(int i=L[qr]+1;i<=R[qr];i++){
p[i]=(1ll*p[i-1]*base+a[i])%mod;
}
for(int i=ql;i<=cnt;i++){
q[i]=(1ll*q[i-1]*pw[R[i]-L[i]+1]+(p[R[i]]+1ll*sumpw[R[i]-L[i]]*del[i])%mod)%mod;
}
}
int get(int x){
int qx=bel[x];
return (1ll*q[qx-1]*pw[x-L[qx]+1]+p[x]+1ll*sumpw[x-L[qx]]*del[qx])%mod;
}
int get(int x,int y){
return (get(y)-1ll*get(x-1)*pw[y-x+1]%mod+mod)%mod;
}
}d;
int cmp(int x,int y,int z,int op){
int l=1,r=z-max(x,y)+1,mid,now=0;
while(l<=r){
mid=(l+r)>>1;
if(d.get(x,x+mid-1)==d.get(y,y+mid-1)){
now=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
if(now==z-max(x,y)+1){
return op;
}
return d.get(x+now,x+now)<d.get(y+now,y+now);
}
void pushup(int rt,int r){
int now=0;
v[rt]=v[rt<<1|1];
for(auto i:v[rt<<1]){
if(!now||cmp(i,now,r,1)){
now=i;
}
}
v[rt].push_back(now);
}
void build(int l,int r,int rt){
int mid=(l+r)>>1;
if(l==r){
v[rt].push_back(l);
return;
}
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt,r);
}
void update(int x,int y,int z,int l,int r,int rt){
int mid=(l+r)>>1;
if(x<=l&&y>=r){
return;
}
if(x<=mid){
update(x,y,z,l,mid,rt<<1);
}
if(y>=mid+1){
update(x,y,z,mid+1,r,rt<<1|1);
}
pushup(rt,r);
}
void query(int x,int y,int l,int r,int rt){
int mid=(l+r)>>1;
if(x<=l&&y>=r){
for(auto i:v[rt]){
if(!ans||cmp(i,ans,y,0)){
ans=i;
}
}
return;
}
if(y>=mid+1){
query(x,y,mid+1,r,rt<<1|1);
}
if(x<=mid){
query(x,y,l,mid,rt<<1);
}
}
int main(){
int m,op,x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
a[i]+=maxx;
}
d.init();
build(1,n,1);
while(m--){
scanf("%d%d%d",&op,&x,&y);
if(op==1){
scanf("%d",&op);
d.update(x,y,op);
update(x,y,op,1,n,1);
}
else{
ans=0;
query(x,y,1,n,1);
printf("%d\n",ans);
}
}
}
Lyndon 数组
定义
一个字符串 \(s\) 的 Lyndon 数组 \(p\) 的定义如下：\(p_i\) 是使得 \(s[i,p_i]\) 为 Lyndon 串的最大的 \(p_i\)。
求解
我们从后往前扫 \(s\)，维护当前后缀的 Lyndon 分解。每次加入一个字符就从前往后扫 Lyndon 串，看能不能合并。合并次数最多为 \(|s|-1\)，使用二分 + 哈希即可。时间复杂度 \(O(|s|\log|s|)\)。若使用 SA-IS 和四毛子 RMQ，则复杂度为 \(O(|s|)\)。
例题
QOJ #7406 Longest Lyndon Prefix
板子题，求 \(s\) 的每个后缀的最长 Lyndon 前缀。\(|s|\leq 10^5\)。
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N=100010;
const ull base=31;
char s[N];
int p[N],ans[N];
ull h[N],pw[N];
ull get(int l,int r){
return h[r]-h[l-1]*pw[r-l+1];
}
int cmp(int a,int b,int c,int d){
int l=1,r=min(b-a+1,d-c+1),mid,ans=0;
while(l<=r){
mid=(l+r)>>1;
if(get(a,a+mid-1)==get(c,c+mid-1)){
ans=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
if(ans==min(b-a+1,d-c+1)){
return (ans==d-c+1)?0:1;
}
return s[a+ans]<s[c+ans];
}
int main(){
int t,n;
scanf("%d",&t);
pw[0]=1;
while(t--){
scanf("%d%s",&n,s+1);
for(int i=1;i<=n;i++){
pw[i]=pw[i-1]*base;
h[i]=h[i-1]*base+s[i];
}
for(int i=n;i>=1;i--){
p[i]=i+1;
while(p[i]<=n&&cmp(i,p[i]-1,p[i],p[p[i]]-1)){
p[i]=p[p[i]];
}
ans[i]=p[i]-i;
}
for(int i=1;i<=n;i++){
printf("%d ",ans[i]);
}
printf("\n");
}
}
Runs
定义
定义长为 \(n\) 的字符串 \(s\) 的 runs 为符合下列条件的子串 \(t\) 的集合：
-
\(t\) 存在长度为 \(p\) 的最小周期，且周期至少完整出现 \(2\) 次。
-
\(t\) 不可向两段扩展，即 \(t\) 是极长的。
求解
显然，一个 run 有 \(p\) 个周期，其中有且仅有一个本质不同的 Lyndon 串。我们把它称为这个 run 的 Lyndon root。如果我们求出了一个 run \(s[l,r]\) 的 Lyndon root \(s[i,j]\)，我们只需要求出 \(s[1,i-1]\) 和 \(s[1,j]\) 的最长公共后缀，还有 \(s[1,i]\) 和 \(s[1,j+1]\) 的最长公共前缀并检查是否出现至少 \(2\) 次即可求出这个 run。
注意到对于 \(i\) 而言， \(s[j+1,n]\) 是第一个比 \(s[i,n]\) 大的后缀。注意到 \(s[i,n]\) 和 \(s[j+1,n]\) 的大小关系与 \(s_{r-p+1}\) 和 \(s_{r+1}\) 的大小关系相同。显然 \(s_{r-p+1}\ne s_{r+1}\)。 所以我们只要对于每个 \(i\) 求出它后面第一个比它大的后缀（这就是 Lyndon 数组）即可求出 \(s_{r-p+1}<s_{r+1}\) 的所有 runs。同样地，我们把字符大小关系反转即可求出 \(s_{r-p+1}>s_{r+1}\) 的所有 runs。最后去重即可。注意到这也给出了 runs 的个数 \(\leq 2n\) 的证明。
事实上，runs 的个数 \(<n\)。这里暂不证。
时间复杂度 \(O(n\log n)\)。如果线性求 Lyndon 数组则为 \(O(n)\)。
例题
P6656 【模板】Runs
板子。
#include<bits/stdc++.h>
using namespace std;
const int N=1000010,base=41,mod=1e9+9;
int n,p[N],h[N],pw[N];
char s[N];
struct runs{
int l,r,len;
bool operator<(runs b){
if(l!=b.l){
return l<b.l;
}
return r<b.r;
}
bool operator==(runs b){
return l==b.l&&r==b.r&&len==b.len;
}
};
vector<runs>ans;
void init(){
pw[0]=1;
for(int i=1;i<=n;i++){
h[i]=(1ll*h[i-1]*base+s[i])%mod;
pw[i]=1ll*pw[i-1]*base%mod;
}
}
int get(int l,int r){
return (h[r]-1ll*h[l-1]*pw[r-l+1]%mod+mod)%mod;
}
int lcs(int x,int y){
int l=1,r=min(x,y),mid,ans=0;
if(s[x]!=s[y]){
return 0;
}
while(l<=r){
mid=(l+r)>>1;
if(get(x-mid+1,x)==get(y-mid+1,y)){
l=mid+1;
ans=mid;
}
else{
r=mid-1;
}
}
return ans;
}
int lcp(int x,int y){
int l=1,r=n-max(x,y)+1,mid,ans=0;
if(s[x]!=s[y]){
return 0;
}
while(l<=r){
mid=(l+r)>>1;
if(get(x,x+mid-1)==get(y,y+mid-1)){
l=mid+1;
ans=mid;
}
else{
r=mid-1;
}
}
return ans;
}
int cmp(int a,int b,int c,int d){
int l=1,r=min(b-a+1,d-c+1),mid,ans=0;
while(l<=r){
mid=(l+r)>>1;
if(get(a,a+mid-1)==get(c,c+mid-1)){
ans=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
if(ans==min(b-a+1,d-c+1)){
return (ans==d-c+1)?0:1;
}
return s[a+ans]<s[c+ans];
}
void add(int x,int y){
int l=lcs(x-1,y-1),r=lcp(x,y);
if((y+r-1)-(x-l)+1>=2*(y-x)){
ans.push_back({x-l,y+r-1,y-x});
}
}
int main(){
scanf("%s",s+1);
n=strlen(s+1);
init();
for(int i=n;i>=1;i--){
p[i]=i+1;
while(p[i]<=n&&cmp(i,p[i]-1,p[i],p[p[i]]-1)){
p[i]=p[p[i]];
}
add(i,p[i]);
}
for(int i=1;i<=n;i++){
s[i]=25-(s[i]-'a')+'a';
}
init();
for(int i=n;i>=1;i--){
p[i]=i+1;
while(p[i]<=n&&cmp(i,p[i]-1,p[i],p[p[i]]-1)){
p[i]=p[p[i]];
}
add(i,p[i]);
}
sort(ans.begin(),ans.end());
ans.erase(unique(ans.begin(),ans.end()),ans.end());
printf("%d\n",ans.size());
for(auto i:ans){
printf("%d %d %d\n",i.l,i.r,i.len);
}
}
参考文献
[1]. https://zhuanlan.zhihu.com/p/664357638
[2]. https://www.cnblogs.com/ptno/p/16418308.html
[3]. https://www.cnblogs.com/zght/p/13443305.html
[4]. https://www.luogu.com/article/d4y3zqqv
标签：int,mid,Lyndon,leq,ans,字符串,杂项 From： https://www.cnblogs.com/zhicheng123/p/18227670