定义
Run
有一个三元组run=(l,r,p)，其中l,r表示在字符串的s[l,r]区间，p表示在s[l,r]中字符串的字串的最小循环节
注意：
-
不存在扩展性，也就是说s[l-1]!=s[l+p-1],s[r+1]!=s[r-p+1],如果成立的话整个三元组会整体右移或者左移，或者向两边同时扩展
-
2p\leq r-l+1
其中run的指数（即循环串出现的次数）e_r=\frac{r-l+1}{p}
\rho_{run}(n)表示长度为n的字符串中其子串能够构成三元组Run的个数
\sigma_{run}(n)表示长度为n的字符串的子串构成的三元组的指数和最大 最大的原因是因为p的定义是最小循环节 ，即\sum_{k=1}^{t}\frac{r_k-l_k+1}{p_k}，其中t为三元组个数(不就是\rho_{run}(n)吗)
Lyndon根
在三元组run=(l,r,p)表示的区间里面，长度为p的Lyndon串
即run的所有循环节中最小表示的的那一个
一个Run里面最少存在一个Lyndon根,证明显然
若run=(l,r,p)的lyndon根s[u,u+p-1]满足u!=l,那么其为真Lyndon根
重载大小运算
<_0：在<_0下a<b,记作a<_0b
<_1：在<_1下b<a,记作b<_1a
其中a,b均为字符
Lyndon数组
l_t[i]表示在<_t的情况下,左端点为i的最长Lyndon串的右端点
性质
性质1：周期相同的run的交长度小于p
证明：若大于p，在交集中可以选择一个循环节进行扩展，即为上述不存在扩展性
性质2：l_0[i]和l_1[i]都存在一个i的值等于i，位置不重合
证明显然
性质3：对于一个三元组Run=(l,r,p)，假设s[r+1]<_ts[r+1-p],那么任意Lyndon根s[u,u+p-1]都有l_t(u)=u+p-1
证明：对于一个s[u,v],u+p-1<v\leq j，满足其形式为w^k+w^`，对于v>j,不存在Lyndon串
性质4：s[u,l_0(u)],s[u,l_1(u)]不可能同时为两个run的Lyndon根
证明：设l_0(u)=u，那么有s[u]=s[u-1]+s[u+p-1]=s[l1(u)],故s[u,l_1(u)]不是Lyndon串
性质5：任意两个不同的run的真Lyndon根的左端点集合不相交
证明见上
Runs定理
Runs定理如下:
\rho_{run}(n)<n,\sigma_{run}(n)<3n
证明：
设B(r)表示三元组Run的所有真Lyndon串的左端点集合，有任意B(r_1)\cap B(r_2)，所以\sum_rB(r)\leq n-1，又因为B(r)\geq 1所以\rho_{run}(n)<n
若r=(l,r,q)循环了x次，其真Lyndon根至少有x-1个，故|B(r)|>e_r-2,\sum_r(e_r-2)<=n-1,所以\sigma_{run}(n)<3n
Runs的求解
算法1
枚举周期p，然后在串中间打标记（每隔长度p打一次），大小为p的run一定会穿过两个点，相邻两个点之间求lcp，如果能够将范围连起来就找到一个
struct STRUCT{
ll sa[M],rk[M],hei[M],lim=125;
ll num[M],x[M],y[M];
ll lg[M],st[M][21];
void init_sa(char *s){
lim=125;
for(ll i=1;i<=n;i++)num[x[i]=s[i]]++;
for(ll i=2;i<=lim;i++)num[i]+=num[i-1];
for(ll i=n;i>=1;i--)sa[num[x[i]]--]=i;
for(ll k=1;k<=n;k<<=1){
ll sum=0;
for(ll i=n-k+1;i<=n;i++)y[++sum]=i;
for(ll i=1;i<=n;i++)if(sa[i]>k)y[++sum]=sa[i]-k;
for(ll i=1;i<=lim;i++)num[i]=0;
for(ll i=1;i<=n;i++)num[x[i]]++;
for(ll i=1;i<=lim;i++)num[i]+=num[i-1];
for(ll i=n;i>=1;i--){