参考资料
0. 一些记号
一些通用的记号
- 字符串下标从 (1) 开始。用 (s_i) 表示 (s) 的第 (i) 个字符，(|s|) 表示字符串 (s) 的总长度。
- (Sigma) 表示字符集大小，(Sigma^*) 表示定义在 (Sigma) 上的字符串。(epsilon) 表示空串。($) 表示特殊字符，且 (forall cinSigma , $ >c)。
- (overlineSigma=Sigmacup{$})，(overline{Sigma^*}) 表示定义在 (overline{Sigma}) 上的特殊字符串。(Sigma^{+}) 表示 (Sigma^*/{epsilon})，即去掉空串。
- 默认 (s_iinSigma^*)，即普通字符串中不存在特殊字符。
- (st)，(s+t) 均表示将字符串 (s) 和字符串 (t) 按顺序拼接得到的字符串。
- (s^k) 表示将 (s) 重复 (k) 遍得到的字符串。(s^{infty}) 表示赋值无数遍得到的字符串。
- (s^{R}) 表示将 (s) 翻转后得到的字符串。
- (s[i:j]) 表示由区间 ([i,j]) 中的字符构成的子串，若 (l>r, s[l:r]=epsilon)。(s[1:i]) 简写为 (s[:i])，(s[i:|s|]) 简写为 (s[i:])。
- (s<t) 表示比较 (s) 和 (t) 的字典序。
- (<^{$})：绝对小于，(u<^{$}) 等价于 (u+$<v)。(>^{$}) 等价于 (u>v+$)。
一些定义
- (operatorname{lcp}(s,t))：(s) 和 (t) 的最长公共前缀。
- ( ext{period})：整数 (l) 是 (s) 的一个 ( ext{period})，当且仅当 (forall iin[1,|s-l|],s_{i}=s_{i+l})。
- ( ext{border})：整数 (l) 是 (s) 的一个 ( ext{border})，当且仅当 (forall iin[1,l],s_{i}=s_{n-l+1})。
- 整循环串：(s) 是一个整循环串当且仅当 (exists tinSigma^* , s=t^k)，其中 (k) 是任意整数。
- 循环串：(s) 是一个循环串当且仅当 (exists tinSigma^*, s=t^k+t[:p])，其中 (k) 是任意整数，(p<|t|)。
- 最短循环节：长度最小的 (t) 满足循环串 (s) 的定义式。
1. ( ext{Lyndon Word})
- ( extbf{Lyndon Word}) ：(s) 是一个 ( ext{Lyndon Word}) 当且仅当 (s) 比其所有后缀中字典序都小。即 (forall i>1,s[1:i])。
比如 ( exttt{ababb}) 就是一个 ( ext{Lyndon Word})。而 ( exttt{abab}) 则不是，因为 ( exttt{ab}< exttt{abab})。
1.1 一些基本性质
- 性质 1：若 (u<^{$}v)，则 (forall w_1,w_2in Sigma^* , u+w_1<v+w_2)。
- 性质 2：若 (s) 是一个 ( ext{Lyndon Word})，(forall i<|s|,s[1:i]<^{$}s[n-i+1:n])。
根据定义显然得证。
- 性质 3：对于两个 ( ext{Lyndon Word} u,v)，若 (u<v)，则 (u+v) 仍是一个 ( ext{Lyndon Word})。
证明：令 (w=u+v)。
任取 (v) 的一个后缀 (v'=v[i:])，若 (|v'|leq |u|) 或 (u<^{$}v)，则有 (u<^{$}v')，故 (w<v)。
否则有 (u=v[1:|u|])。假设有 (w>v)，对于 (l=|v|-|u|)，有 (v[:l]geq v[n-l+1:])，与性质 2 不符。
故 (w) 小于 (v) 中的任何一个后缀。
再任取 (u) 的一个后缀 (u'=u[i:])，由于 (u>^{$}u')，故 (w>u'+v)。
至此我们证明了 (w) 是一个 ( ext{Lyndon Word}) 。
1.2 ( ext{Lyndon}) 分解
- ( extbf{Lyndon}) 分解：把一个字符串分解为若干个 ( ext{Lyndon Word})，并且字典序单调不增。
形式化说，构造一个序列 (t_i)，使 (t_1+t_2+cdots+t_n=s)，且 (forall i , t_i) 是一个 ( ext{Lyndon Word})。
通常 ( ext{Lyndon}) 分解采用 Duval 算法。
算法思路
考虑将字符依次加入，维护当前的 ( ext{Lyndon}) 分解：
我们假设分解形式为 (T+t'^k+t'[:p])，其中 (T=t_1+t_2+cdots+t_{i})。保证有 (t_1geq t_2geq cdots geq t_{i}>t')。
考虑我们加入一个字符 (c)，设 (v) 表示 (t'[:pmod |t'|+1])，如果：
- (c=v) ：转移到分解 (T+t'^k+t'[:p+1])（如果 (p=|t'|) 则是 (T+t'^{k+1})）。
- (c<v , t'[:p]+c<t') ：令 (jin[1,k],s_{i+j}=t')，转移到 (T'+(t'[:p]+c))。
- (c>v , t'^k+t'[:p]+c) 是一个 ( ext{Lyndon Word}) ：令 (s_{i+1}=t'^k+t'[:p]+c)，转移到 (T')。，复杂度 (O(n))。
具体实现
考虑到 (t'^k+t'[:p]) 本质是一个循环串，故维护三个变量 ((i,j,k))，其中 (i) 是首字母位置，([j,k]) 是最后一个循环节的位置。
这样对于情况一，令 (i+1,j+1)。情况二则从 (i) 开始每 (k-j+1) 划分一个分解。情况三则令 (j=i)。
代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 5000010
using namespace std;
char s[N];
int p[N],t;
int main()
{
scanf("%s",s+1);
int n=strlen(s+1);
for(int i=1,j=1,k=2;i<=n;j=i,k=i+1)
{
for(;k<=n && s[j]<=s[k];k++)
{
if(s[j]<s[k]) j=i;
else j++;
}
for(;i<=j;i+=k-j) p[++t]=i+(k-j)-1;
}
int ans=0;
for(int i=1;i<=t;i++) ans^=p[i];
printf("%d
",ans);
return 0;
}
1.3 ( ext{Lyndon}) 数组
- ( extbf{Lyndon}) 数组：定义 (lambda_i) 表示从 (i) 开始最长的 ( ext{Lyndon Word}) 。即 (s[i:lambda_i]) 是一个 ( ext{Lyndon Word}) ，且 (forall j>lambda_i , s[i:j]) 不是一个 ( ext{Lyndon Word}) 。
一些性质
- 性质1：若 (u) 是一个 ( ext{Lyndon Word})，(s) 的一组 ( ext{Lyndon}) 分解是 (t_1+t_2+cdots t_n)。那么 (u<t_1) 当且仅当 (u+s<s)。
证明：根据是否有 (u<^{$}t_1) 分类讨论，如果没有再根据是否有 (|u|<t_1)，如果是则递归 (t_2) 讨论，否则可以推出 (t_1) 不是一个 ( ext{Lyndon Word})。
算法实现
从后往前加字符，考虑维护一个单调栈，设 (t_0) 是栈顶，满足 (t_igeq t_{i+1})。对于 (p) 位置新加的字符 (c)，我们令 (s'=c)。每次判断是否有 (s'<t_0)。如果有则弹出栈顶，令 (s_m=s_m+t_0)。重复上述步骤直到满足单调性质，此时的 (s_m) 的右端点即 (lambda_p)。
使用Hash+二分处理两个串的大小关系可以做到 (O(nlog n)) 的复杂度。若使用 SA-IS 加 (O(n)-O(1)) ST表可以做到 (O(n)) 的时间复杂度。
2. ( ext{Runs})
- ( extbf{period})： 定义一个整数 (p) 是一个字符串 (s) 的 ( ext{period}) ，当且仅当 (forall iin[1,|s|-p],s_{i}=s_{i+p})。
即某一个字符串不断循环得到 (s)。这里并不一定要整循环，比如 (3) 就是 ( exttt{abbabba}) 的一个 ( ext{period})。
- ( extbf{run})：定义三元组 ((i,j,p)) 是一个 ( ext{run}) ，当且仅当 (s_{j+1} eq s_{j-p+1},s_{i-1} eq s_{i+p-1}) 且 (p) 是 ([i,j]) 最小的出现至少两次的循环节。
比如 ( exttt{ababababba}) 中：
((1,8,2)) 是一个 ( ext{run}) 。
((3,8,2)) 不是，因为这个这个周期串可以继续向左延伸。
((1,8,4)) 不是，因为 (p=4) 不是 (s[1:8]) 的最小 ( ext{period})。
((6,10,3)) 不是，因为 (p=3) 没有出现至少两次，即 (p>frac{10-6+1}{2})。
一些定义
-
( extbf{Runs}) ：定义 ( ext{Runs}(s)) 是字符串 (s) 的所有 ( ext{run}) 的集合。
-
指数：定义一个 ( ext{run}) ((l,r,p)) 的指数是 (frac {r-l+1} p)，即 ( ext{period}) (p) 在 (s[l:r]) 中的出现次数。记作 (e_{(l,r,p)})。
-
定义两种偏序关系 (<_0,<_1)。由于只要满足 (a<_0 b ightarrow b<_1 a)，所以一般这里 (<_0) 表示“字典序较小”，(<_1) 表示“字典序较大”。一般我们认为空字符字典序最小，即 (varnothing<_0 exttt{a} , exttt{a}<_0 exttt{aa})。
-
(ellin{0,1}) 表示一种偏序关系，(overline{ell}) 表示与 (ell) 相反的偏序关系，以下 (<_{ell}) 表示 (ell) 对应的偏序关系。
-
( extbf{Lyndon Root})：定义 (s[lambda_l:lambda_r]) 是 ((i,j,p)) 在 (<) 上的 ( ext{Lyndon Root})，当且仅当 ([lambda_l,lambda_r]subseteq [i,j]) 且 (s[lambda_l:lambda_r]) 是一个 ( ext{Lyndon Word})。
-
(B(r)) 表示一个 ( ext{run}) (r) 的所有除去开头的 ( ext{Lyndon Root}) 的集合。即集合中的元素 (s[i:j]) 要求 (i eq r_l)。显然有 (|B(r)|geq lfloor e_r-1 floorgeq 1)。
-
( ext{Beg}(B(r))) 表示 (B(r)) 的所有起始端点组成的集合。
-
(l_{ell}(i)) 表示所有从 (i) 开始的 ( ext{Lyndon Word}) 中最长的那个。即 (l_{ell}(i)=[i,j],j=max{j'|s[i:j'] ext{是一个 Lyndon Word}})。
-
(overline{s}=s+$)，即末尾多一个特殊字符。
-
( ext{run}) ((i,j,p)) 是 (ell(ellin{0,1})) 型的，当且仅当 (s_{j-p+1}<_{ell}s_{j+1})。
一些推论
- 引理1：对于字符串 (s=t^kt[:p])，其中 (t) 是一个 ( ext{Lyndon Word})，(t[:p]) 表示 (t) 的一个前缀且在这里允许为空。现在在其后加入字符 (a) 且 (a eq t_{p+1})。如果 (a<t_{p+1}) 那么 (s=t^kt[:p]a) 是任意前缀中最长的 ( ext{Lyndon Word})。
这个其实就是上面 ( ext{Lyndon}) 分解所用的结论。
-
推论1：对于 (ell) 型 ( ext{run}) ((i,j,p))，其所有定义在 (<_{ell}) 上的 ( ext{Lyndon Root}) (lambda=[l_{lambda},r_{lambda}]) 都有 (lambda=l_{ell}(l_{lambda}))，即其所有 ( ext{Lyndon Root}) 都是相同起点中最长的 ( ext{Lyndon Root})。
-
推论2：对于任意 ( ext{run}) (r(i,j,p)) ，其所有的 ( ext{Lyndon Root}) 左端点不重复，即有 (| ext{Beg}(B(r))|=|B(r)|)。
-
引理2：对于任意位置 (pin[1,|s|])，有且仅有一个 (ellin{0,1}) 满足 (l_{ell}(i)=overline{s}[i:i])。
证明：找到 (overline{s}[i:]) 第一个与 (overline{s}_i) 不同的位置 (p')。即 (min{p'|p'>i,overline{s}_{p'} eq overline{s}_p})。令 (ell) 满足 (s_{p'}<_{ell}s_p)，由引理1显然有 (l_{ell}=[i,i])，(l_{overline{ell}} eq[i,i])。（此处 WC2019 的课件貌似有误？课件好像取的是 (max)）。
- 推论3：(forall r,r ext{ is a run},r eq r')，有 ( ext{Beg}(B(r)) cap ext{Beg}(B(r'))=varnothing)。
具体证明大概就是根据引理 2 用反证推出如果存在交集，取交集的位置就能推出周期性，与 ( ext{run}) 的定义不符。
-
结论1：任意位置 (p) 最多存在于一个 (Beg(B(r))) 中。由一个 ( ext{Lyndon Root}) 能唯一确定一个 ( ext{run}) (r)。由于 (forall r,1 otin ext{Beg}(B(r))) 故 (sum| ext{Beg}(B(r))|leq n-1)，故有 (| ext{Runs}(s)|<|s|)。
-
结论2：由于 ( ext{Beg}(B(r))>e_r-1)。由结论 1 可推得 (sum{e_r}leq 3n-3)。
接下来考虑如何快速求的 ( ext{Runs}(s))。
考虑我们先求出 (l_{ell}(i))，即以 (i) 开头最长的 ( ext{Lyndon Word})。容易发现这个就是 1.3 ( extbf{Lyndon}) 数组。
获得了所有 (l_{ell}(i)) 后，我们令 (p=l_{ell}(i)-i+1)，观察其向左向右能延伸到的最远的地方 ([l',r'])。对于三元组 ((l',r',p))，我们只需要判断其是否满足 (pleq frac{r'-l'+1} 2) 即可。
实现细节：一种比较 ( ext{simple}) 的方式是用 Hash+二分处理两个串的 ( ext{lcp}/ ext{lcs})。对于子串大小比较直接比较 ( ext{lcp}) 的后一位即可。判断延伸到的最远的位置 ([l',r'])，可以发现对于 (l') 一定有 (s[l':i]=s[l'+p-1:s+p-1])，所以直接取 (s[:i],s[:l_{ell}(i)]) 的 ( ext{lcp}) 即可。(r') 同理。这样总复杂度是 (O(nlog n))。
上述复杂度瓶颈在于求 ( ext{lcp})。用 SA-IS 套 (O(n)-O(1)) ST表可以优化到 (O(n))。
至此就完成了 ( ext{Runs}) 的求解。
LOJ173 Runs
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define N 1000010
#define ull unsigned long long
#define B 2333
using namespace std;
char str[N];
int s[N],n;
ull h[N],bs[N];
ull get(int l,int r){return h[r]-h[l-1]*bs[r-l+1];}
int lcp(int x,int y)
{
int l=1,r=n-max(x,y)+1,res=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(get(x,x+mid-1)==get(y,y+mid-1)) l=mid+1,res=mid;
else r=mid-1;
}
return res;
}
int lcs(int x,int y)
{
int l=1,r=min(x,y),res=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(get(x-mid+1,x)==get(y-mid+1,y)) l=mid+1,res=mid;
else r=mid-1;
}
return res;
}
bool cmp(int l1,int r1,int l2,int r2)//s[l1:r1]<s[l2:r2]
{
int l=lcp(l1,l2);
if(l>min(r1-l1,r2-l2)) return r1-l1<r2-l2;
return s[l1+l]<s[l2+l];
}
struct runs{
int i,j,p;
runs(int i=0,int j=0,int p=0):i(i),j(j),p(p){}
bool operator ==(const runs a)const{return i==a.i && j==a.j && p==a.p;}
bool operator <(const runs a)const{return i==a.i?j<a.j:i<a.i;}
};
vector<runs>ans;
int st[N],t,run[N];
void lyndon()
{
t=0;
for(int i=n;i;i--)
{
st[++t]=i;
for(;t>1 && cmp(i,st[t],st[t]+1,st[t-1]);t--);
run[i]=st[t];
}
}
void init()
{
bs[0]=1;
for(int i=1;i<=n;i++) h[i]=h[i-1]*B+s[i],bs[i]=bs[i-1]*B;
}
void get_runs()
{
for(int i=1;i<=n;i++)
{
int l1=i,r1=run[i],l2=l1-lcs(l1-1,r1),r2=r1+lcp(l1,r1+1);
if(r2-l2+1>=(r1-l1+1)*2) ans.push_back(runs(l2,r2,r1-l1+1));
}
}
int main()
{
scanf("%s",str+1);
n=strlen(str+1);
for(int i=1;i<=n;i++) s[i]=str[i]-'a'+1;
init();
lyndon();
get_runs();
for(int i=1;i<=n;i++) s[i]=27-s[i];
lyndon();
get_runs();
sort(ans.begin(),ans.end());
ans.erase(unique(ans.begin(),ans.end()),ans.end());
printf("%d
",(int)ans.size());
for(auto u:ans) printf("%d %d %d
",u.i,u.j,u.p);
return 0;
}