模板：P6114 【模板】Lyndon 分解＆Runs（字符串）

你不会连跑步都不会吧。

（逃

前言

SAM：runs？那我run了。

比 SAM 看起来层次更高的奥妙算法。
理论证明比较复杂，但板子写起来都比较简单。
本文会略过很多的证明。

Lyndon 分解

Definition：
如果一个串本身比它的所有真后缀字典序都小，我们就称这样的一个串为 Lyndon 串。
如果一个字符串的划分 $w_1{w}_2...w_k$ 满足所有的 w 都是 Lyndon 串，且满足字典序 $w_1\ge w_2\ge ...\ge w_k$，则成其为字符串的 Lyndon 分解。

可以证明，任意字符串的 Lyndon 分解是唯一的。

求解

如何求呢？
设考虑到第 i 位。
此时未确定的分解必然形如 $www...w^{\prime }$，$w^{\prime }$ 是 $w$ 的一个前缀。
如果新字符和循环节对应位置相同，不做处理。
如果新字符更大，合并成一整块。
如果新字符更小，把前面的若干个循环节分裂出来，然后回退到 $w^{\prime }$，继续处理。
时间复杂度 $O(n)$。

int i=1,j=2,l=1,res(0);
for(;i<=n;j++){
    
  if(s[j]>s[j-l]) l=j-i+1;
  else if(s[j]<s[j-l]){
    
    while(i+l<=j){
    
		res^=(i+l-1);
		i+=l;		
    }
    j=i;l=1;
  }  
}

Runs

definition:
如果一个字符串的某个字串可以写成 $ppp...p^{\prime }$ 的形式，且其是符合条件的极长子串，则称其为一个 runs。（周期p至少出现两次）
对于每一个runs，其长度恰好为p的lyndon串称为其的 lyndon根。

每个runs有且只有一个本质不同的lyndon根。

Lemma：设 $l{t}_i$ 为 $\max j,s(i,j)为lyndon串$，那么对于一个 lyndon 根(i,j)，在 ${<}_0,{<}_1$ 两种相反的比较符定义下，至少有一种情况满足 $l{t}_i=j$。

所以我们可以求出 $lt$ 数组，然后通过 $(i,l{t}_i)$ 反推出其对应的runs（通过求lcp和lcs容易求出）。

那么如何求出 $lt$ 呢？
lyndon 分解还有一种单调栈的求法，当栈顶字典序小于当前元素时不断把栈顶块和当前块合并。不难发现此时得到的块的右端点就是对应的 $l{t}_i$。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")

inline ll read() {
    
  ll x(0),f(1);char c=getchar();
  while(!isdigit(c)) {
    if(c=='-') f=-1;c=getchar();}
  while(isdigit(c)) {
    x=(x<<1)+(x<<3)+c-'0';c=getchar();}
  return x*f;
}
const int N=1e6+100;
const int mod=1e9+7;
const int inf=1e9+100;
const double eps=1e-9;

bool mem1;

bool Flag=0;

inline ll ksm(ll x,ll k,int mod){
    
  ll res(1);
  x%=mod;
  while(k){
    
    if(k&1) res=res*x%mod;
    x=x*x%mod;
    k>>=1;
  }
  return res;
}

int n,m;
char s[N];
const int bas=31;
ull h[N],mi[N];
void init(){
    
  mi[0]=1;
  for(int i=1;i<=n;i++){
    
    mi[i]=mi[i-1]*bas;
    h[i]=h[i-1]*bas+s[i]-'a'+1;
  }
  return;
}
inline ll Hash(int l,int r){
    
  return h[r]-mi[r-l+1]*h[l-1];
}
inline int lcp(int i,int j){
    
  int st=0,ed=n-max(i,j)+1;
  while(st<ed){
    
    int mid=(st+ed+1)>>1;
    if(Hash(i,i+mid-1)==Hash(j,j+mid-1)) st=mid;
    else ed=mid-1;
  }
  return st;
}
inline int lcs(int i,int j){
    
  int st=0,ed=min(i,j);
  while(st<ed){
    
    int mid=(st+ed+1)>>1;
    if(Hash(i-mid+1,i)==Hash(j-mid+1,j)) st=mid;
    else ed=mid-1;
  }
  return st;
}
map<int,int>mp[N];
struct run{
    
  int l,r,p;
  bool operator < (const run &oth)const{
    
    if(l!=oth.l) return l<oth.l;
    else return r<oth.r;
  }
};
vector<run> ans;
inline void ins(int i,int j){
    
  if(j==n) return;
  j++;
  int p=(j-i),pre=i-lcs(i,j)+1,suf=j+lcp(i,j)-1;
  //printf("ins: (%d %d) (%d %d)\n",i,j,pre,suf);
  if(mp[pre][suf]) return;
  if(suf-pre+1>=2*p){
    
    mp[pre][suf]=1;
    ans.emplace_back((run){
    pre,suf,p});
  }
  return;
}
int cmp(int i,int j,int x,int y){
    //i<j?
  int len=lcp(i,j);
  //printf("i=%d j=%d x=%d y=%d len=%d\n",i,j,x,y,len);
  if(len>=min(x,y)){
    
    if(x<y) return 1;
    else if(x==y) return 0;
    else return -1;
  }
  else{
    
    if(s[i+len]<s[j+len]) return 1;
    else if(s[i+len]==s[j+len]) return 0;
    else return -1;
  }
}
int zhan[N],top;//zhan:right pos
void work(){
    
  top=0;
  for(int i=n;i>=1;i--){
    
    int pos=i;
    while(top&&cmp(i,pos+1,pos-i+1,zhan[top]-pos)==1) pos=zhan[top--];
    //if(top) printf(" f=%d\n",cmp(i,pos+1,pos-i+1,zhan[top]-pos));
    zhan[++top]=pos;
    //printf("i=%d pos=%d\n",i,pos);
    ins(i,pos);
  }  
}

bool mem2;
signed main(){
    
#ifndef ONLINE_JUDGE
  freopen("a.in","r",stdin);
  freopen("a.out","w",stdout);
#endif
  scanf("%s",s+1);
  n=strlen(s+1);
  init();
  work();
  for(int i=1;i<=n;i++) s[i]='a'-s[i]+1;
  work();
  sort(ans.begin(),ans.end());
  printf("%d\n",(int)ans.size());
  for(run o:ans) printf("%d %d %d\n",o.l,o.r,o.p);
  return 0;
}
/* */