Lyndon 分解&最小表示法

· · 个人记录

Lyndon 分解

P6114 【模板】Lyndon 分解

### $Duval$ 算法 题目让我们将原串分解成一些 $Lyndon$ 串，并且使得 $s_{i} \ge s_{i+1}$（前一个子串字典序大于后面字串的字典序），这种分解是唯一的。 我们处理的时候定义两个指针，$j=i,k=i+1$。其中 $i$ 是上一次处理完的结尾。 我们将 $j,k$ 向后找，如果 $s[j]>s[k]$ 那么跳出循环，因为如果继续就不是 $Lyndon$ 串了。 如果 $s[j]<s[k]$ 就将 $j=i$，返回块的开头，将已经有的块合并，已经有的 $k-j+1$ 和新的块 $j-i$。 如果 $s[j]=s[k]$ 就保持，继续找即可。 ### 题解 ```cpp #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> #include<queue> #include<vector> #include<random> #include<ctime> using namespace std; long long r_r(){//快读 long long k=0,f=1; char c=getchar(); while(!isdigit(c)){ if(c=='-')f=-1; c=getchar(); } while(isdigit(c)){ k=(k<<1)+(k<<3)+(c^48); c=getchar(); } return k*f; } const int o_o=5e6+10; char s[o_o]; int n,a_s; int main(){ 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]){//如果 s[j]>s[k] 就不是 Lyndon 串 if(s[j]<s[k])j=i;//合并 else j++;//保持循环 k++;//整个序列往后比对 } while(i<=j){ a_s^=i+k-j-1;//累计块长的右端点 i+=k-j;//下一个块 } } printf("%d\n",a_s);//输出结果 return 0; } ``` ## 最小表示法 [P1368 【模板】最小表示法](https://www.luogu.com.cn/problem/P1368) 大体思路，定义两个变量，代表两个字符的开头，然后比对两个字符串，不优的从不优的地方重新最为新串的头比对，最后找到最有的开头。 例子： $s=abcababb

两个开头：i=0,j=1，开始比对：

$s[0]<s[2]$ 更新（$j=3$）： $s[0]==s[3],s[1]==s[4],s[2]>s[5]$。 其中比对时，开头不变，用一个辅助变量 $k$，比较：$s[i+k]$ 和 $s[j+k]$。 $i$ 更新：$i=i+k+1=0+3+1=4…

到边界后可以往后延伸，注意取余判断。如果字符串的开头要取余跑回前面继续找，那么结束比对，直接使用当前最优开头即可。

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<vector>
#include<random>
#include<ctime>
using namespace std;
long long r_r(){//快读 
    long long k=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        k=(k<<1)+(k<<3)+(c^48);
        c=getchar();
    }
    return k*f;
} 
const int o_o=3e5+10;
const int m_a=1e9;
int n,a_s,a_a[o_o];
int f_n(){
    int i=0,j=1;//两个串开头初始化 
    int k=0;//辅助比较变量 
    while(i<n&&j<n&&k<n){
        if(a_a[(i+k)%n]==a_a[(j+k)%n])k++;//两个串相同的地方跳过 
        else{
            //其中一个不优，换新串 
            if(a_a[(i+k)%n]>a_a[(j+k)%n])i+=k+1; 
            else j+=k+1;
            if(i==j)i++;//保证不相等 
            k=0;//重心从第一位开始比较 
        }
    }
    return min(i,j);//返回更小的值 
}
int main(){
    n=r_r();
    for(int i=0;i<n;i++)a_a[i]=r_r();//读入序列 
    a_s=f_n();//找到开头 
    for(int i=0;i<n;i++)//输出序列 
        printf("%d ",a_a[(i+a_s)%n]);
    return 0;
}

Lyndon 分解做法

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<vector>
#include<random>
#include<ctime>
using namespace std;
long long r_r(){//快读 
    long long k=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        k=(k<<1)+(k<<3)+(c^48);
        c=getchar();
    }
    return k*f;
} 
const int o_o=5e6+10; 
int s[o_o];
int n,a_s;
int main(){
    n=r_r(); 
    for(int i=1;i<=n;i++){
        s[i]=r_r();
        s[i+n]=s[i];//复制一份 
    }
    int i=1;
    while(i<=n){
        int j=i,k=i+1;
        while(k<=n*2&&s[j]<=s[k]){
            if(s[j]<s[k])j=i;
            else j++;
            k++;
        }
        while(i<=j){
            i+=k-j;
            if(i<=n)a_s=i;//更新开头（越靠后的字典序越小） 
        }
    }
    for(int i=1;i<=n;i++)printf("%d ",s[a_s-1+i]);
    return 0;
}