Lyndon分解&最小表示法

$Lyndon$ 分解

P6114 【模板】Lyndon 分解

$Lyndon$ 串，可以简单理解为：一个串的所有循环中，$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]$ 就保持，继续找即可。

题解

#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 【模板】最小表示法

大体思路，定义两个变量，代表两个字符的开头，然后比对两个字符串，不优的从不优的地方重新最为新串的头比对，最后找到最有的开头。

例子：

$s=abcababb$

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

$s[0] < s[1],(a < b)$ $j$ 更新：$j=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;
}