dede做手机网站,广州建站招聘,安阳网站建设_,制作网站的工具你不会连跑步都不会吧。 #xff08;逃
前言
SAM#xff1a;runs#xff1f;那我run了。
比 SAM 看起来层次更高的奥妙算法。 理论证明比较复杂#xff0c;但板子写起来都比较简单。 本文会略过很多的证明。
Lyndon 分解 Definition#xff1a; 如果一个串本身比它的所… 你不会连跑步都不会吧。 逃
前言
SAMruns那我run了。
比 SAM 看起来层次更高的奥妙算法。 理论证明比较复杂但板子写起来都比较简单。 本文会略过很多的证明。
Lyndon 分解 Definition 如果一个串本身比它的所有真后缀字典序都小我们就称这样的一个串为 Lyndon 串。 如果一个字符串的划分 w1w2...wkw_1w_2...w_kw1w2...wk 满足所有的 w 都是 Lyndon 串且满足字典序 w1≥w2≥...≥wkw_1\ge w_2\ge ...\ge w_kw1≥w2≥...≥wk则成其为字符串的 Lyndon 分解。 可以证明任意字符串的 Lyndon 分解是唯一的。
求解
如何求呢 设考虑到第 i 位。 此时未确定的分解必然形如 www...w′www...wwww...w′w′ww′ 是 www 的一个前缀。 如果新字符和循环节对应位置相同不做处理。 如果新字符更大合并成一整块。 如果新字符更小把前面的若干个循环节分裂出来然后回退到 w′ww′继续处理。 时间复杂度 O(n)O(n)O(n)。
int i1,j2,l1,res(0);
for(;in;j){if(s[j]s[j-l]) lj-i1;else if(s[j]s[j-l]){while(ilj){res^(il-1);il; }ji;l1;}
}Runs definition: 如果一个字符串的某个字串可以写成 ppp...p′ppp...pppp...p′ 的形式且其是符合条件的极长子串则称其为一个 runs。周期p至少出现两次 对于每一个runs其长度恰好为p的lyndon串称为其的 lyndon根。 每个runs有且只有一个本质不同的lyndon根。 Lemma设 ltilt_ilti 为 maxj,s(i,j)为lyndon串\max j,s(i,j)为lyndon串maxj,s(i,j)为lyndon串那么对于一个 lyndon 根(i,j)在 0,1_0,_10,1 两种相反的比较符定义下至少有一种情况满足 ltijlt_ijltij。 所以我们可以求出 ltltlt 数组然后通过 (i,lti)(i,lt_i)(i,lti) 反推出其对应的runs通过求lcp和lcs容易求出。
那么如何求出 ltltlt 呢 lyndon 分解还有一种单调栈的求法当栈顶字典序小于当前元素时不断把栈顶块和当前块合并。不难发现此时得到的块的右端点就是对应的 ltilt_ilti。
#includebits/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 cgetchar();while(!isdigit(c)) {if(c-) f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N1e6100;
const int mod1e97;
const int inf1e9100;
const double eps1e-9;bool mem1;bool Flag0;inline ll ksm(ll x,ll k,int mod){ll res(1);x%mod;while(k){if(k1) resres*x%mod;xx*x%mod;k1;}return res;
}int n,m;
char s[N];
const int bas31;
ull h[N],mi[N];
void init(){mi[0]1;for(int i1;in;i){mi[i]mi[i-1]*bas;h[i]h[i-1]*bass[i]-a1;}return;
}
inline ll Hash(int l,int r){return h[r]-mi[r-l1]*h[l-1];
}
inline int lcp(int i,int j){int st0,edn-max(i,j)1;while(sted){int mid(sted1)1;if(Hash(i,imid-1)Hash(j,jmid-1)) stmid;else edmid-1;}return st;
}
inline int lcs(int i,int j){int st0,edmin(i,j);while(sted){int mid(sted1)1;if(Hash(i-mid1,i)Hash(j-mid1,j)) stmid;else edmid-1;}return st;
}
mapint,intmp[N];
struct run{int l,r,p;bool operator (const run oth)const{if(l!oth.l) return loth.l;else return roth.r;}
};
vectorrun ans;
inline void ins(int i,int j){if(jn) return;j;int p(j-i),prei-lcs(i,j)1,sufjlcp(i,j)-1;//printf(ins: (%d %d) (%d %d)\n,i,j,pre,suf);if(mp[pre][suf]) return;if(suf-pre12*p){mp[pre][suf]1;ans.emplace_back((run){pre,suf,p});}return;
}
int cmp(int i,int j,int x,int y){//ij?int lenlcp(i,j);//printf(i%d j%d x%d y%d len%d\n,i,j,x,y,len);if(lenmin(x,y)){if(xy) return 1;else if(xy) return 0;else return -1;}else{if(s[ilen]s[jlen]) return 1;else if(s[ilen]s[jlen]) return 0;else return -1;}
}
int zhan[N],top;//zhan:right pos
void work(){top0;for(int in;i1;i--){int posi;while(topcmp(i,pos1,pos-i1,zhan[top]-pos)1) poszhan[top--];//if(top) printf( f%d\n,cmp(i,pos1,pos-i1,zhan[top]-pos));zhan[top]pos;//printf(i%d pos%d\n,i,pos);ins(i,pos);}
}bool mem2;
signed main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifscanf(%s,s1);nstrlen(s1);init();work();for(int i1;in;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;
}
/*
*/
