题解：P6656 【模板】Runs
_zaa_
·
2025-05-29 09:36:10
·
题解
写了一个 O(n\log^2 n) 的做法，在经过不懈的卡空间过后，终于过了。
算法介绍
我们首先看到 AA 串（平方串），一般就是两种方法，一个是 Runs，一个是优秀的拆分中枚举关键点的方法，这是 Runs 模板，肯定可以用 Runs 去做，但是另一种方法也不是不行。首先我们对于长度为 i 的 AA 串，我们可以知道这些串开头的位置，然后我们发现相邻的两个开头的 AA 串一定在一个周期子串内，于是我们可以使用栈将所有开头合并为几个区间，得到了周期为 i 的所有极长周期子串。
然后我们需要去重，因为可能有些如 AAAA 的串周期可以为 |A| 也可以为 |A|\times 2 所以我们先记下所有的周期子串和他的周期，然后如果有一个周期比其小并且包含这个子串，然后并且发现如果这个串被一个周期比其小的子串包含那么这两个一定是同一个子串，证明不难，然后简单排序后去重输出就可以了。
正确性证明
（知道 run 的个数 O(S) 的就可以了，可以略过）
正确性是显然的，但我们来证明上述过程的时间复杂度，由于划分关键点那一段的时间复杂度是固定的，我们只需要证明 run 的个数就可以了。
我们定义 S 的周期长度恰好为 \frac{|S|}{2} 的叫做本原平方串，那么所有 run 的开头都是本原平方串。
首先同一个开头的平方串，如果其中有两个串 pp,qq （|p|<|q|,2\times|p|>|q| ），那么 |q|-|p| 是 p 的周期。
证明：
就这样推推就可以了。
然后我们可以推到：有同一个开头的三个平方串 uu,vv,ww ，且 uu 是本原平方串，则 |u|+|v|\le|w| 。
证明：
不难发现 2\times |v|\le|w| 不用管，那么只需要考虑 2\times |v|>|w| 的情况。
我们能得到 |w|-|v| 是 v 的周期。
然后我们考虑 |u|+|v|>|w| 可不可能。
假设它是成立的，那么我们可以得到 |w|-|v| 是 u 的周期。
然后如果 2|u|\le |v| ，则 uu 是 v 的前缀，然后就可以得到 |w|-|v| 也是 uu 的周期，但是 |w|-|v|<|u| 所以 uu 的最小周期并不是 |u| ，这并不满足本原平方串。
如果 2|u|>|v| ，则 |v|-|u| 是 u 的周期。
（插入一个引理）
然后需要引入一个引理：
如果 p,q 均为 s 的一个周期，且 p+q\le |S| ，则 gcd(p,q) 同样也是 s 的一个周期。
证明：
假设 p<q,a=p-q 。
s_i=s_{i-p}=s_{i-p+q}=s_{i-a}(|s|-q\le i<|s|-a)
s_i=s_{i+q}=s_{i+q-p}=s_{i+a}(0\le i<|s|-q)
然后能得到：s_i=s_{i+a}(0\le i <|s|-a) 。
也就是说 a 也是 s 的周期，然后可以根据辗转相减得到 \gcd(p,q) 也是 s 的周期。
然后发现 |u|,|w|-|v| 实际上都是 v 的周期，但是由于 uu 是一个本原平方串，所以 v 的最小周期不可能 \le\frac{|v|}{2} ，否则 uu 就不是一个本原平方串，但是 |u|,|w|-|v|\le v,|u|\not=|w|-|v| ，所以 \gcd(|u|,|w|-|v|)\le \frac{|v|}{2} ，按理来说 \gcd(|u|,|w|-|v|) 也应该是 v 的周期但是它不是，说明
然后我们画个图：
黄色框代表串 $a$ 长度为 $|w|-|v|$，红色框代表串 $b$ 长度为 $|u|-(|w|-|v|)$，蓝色框代表串 $c$ 长度为 $|v|-|u|$。然后从图中可以得到的的是 $c$ 是 $ab$ 的前缀，$bc$ 是 $ab$ 的前缀。所以 $c$ 是 $bc$ 前缀，然后不难得到 $|b|$ 是 $bc$ 的周期，由于 $u$ 有长度为 $|v|-|u|$ 的周期而且 $c$ 和 $bc$ 都是 $u$ 的前缀，所以 $|c|$ 也是 $bc$ 的周期。不难得到 $\gcd(|b|,|c|)$ 也是 $bc$ 的周期。然后由于 $|a|$ 也是 $u$ 的周期所以 $\gcd(|a|,|b|,|c|)$ 也是 $bc$ 的周期，不难得到 $\gcd(|a|,|b|,|c|)$ 也是 $u$ 的周期。所以 $u$ 不是本原平方串。
故 $|u|+|v|\le|w|$。
#### run 的个数
一个非常明显的东西就是一个 run 的开头一定是一个本原平方串。
然后能得到的是的本质不同的本原平方串最多有 $2n$ 个。
**证明：**
现在我们有相同开头的三个本原平方串 $uu,vv,ww$（$|u|<|v|<|w|$）。然后因为 $|u|+|v|\le |w|$，所以 $|u|\times 2< |w|$。然后 $uu$ 可以在后面可以不在此处计算，而在后面的那个 $w$ 那里计算，所以最多只会有每个开头最多会算两个。
所以 run 的个数是小于等于 $2n$ 的。
## 代码实现
根据上述思路我们可以得到以下代码：
[代码链接](https://www.luogu.com.cn/paste/rzxsegw1)
时间复杂度：$O(n\log n)$。
但是你会发现 MLE 了，数组开小之后能得到 $60$ 分。
我们需要继续优化。
我们发现主要的空间都用在了后缀数组，然后发现 $10^6$ 两秒两只 $\log$ 似乎能过，于是就把后缀数组求 lcp 改成二分 hash，然后发现：
还是 MLE！
然后我们发现 stack 有点占空间，于是将 stack 改成手写的（就是只用一个数组记录栈，然后再记一个数组当栈顶，再记一下每个位置上一个位置）。
然后再将一些数组重复利用就可以了。
```cpp
#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
//#include <immintrin.h>
//#include <emmintrin.h>
#define ls(x) ((x)*2)
#define rs(x) ((x)*2+1)
#define pii pair<int,int>
#define fi first
#define se second
#define Debug(...) fprintf(stderr, __VA_ARGS__)
#define For(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define Rof(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define rep(i, b) for(int i=1,i##end=b;i<=i##end;i++)
using namespace std;
const int N=1e6+5,base=999983,Mod=998244353;
//char buf[(1<<21)+5],*p1,*p2;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline void chmx(int &x,int y){(x<y)&&(x=y);}
inline void chmn(int &x,int y){(x>y)&&(x=y);}
inline void Add(int &x,int y){(x=x+y+Mod)%=Mod;}
inline int read(){
int f=0,x=0;
char ch=getchar();
while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return f?-x:x;
}
void print(int n){
if(n<0){
putchar('-');
n*=-1;
}
if(n>9) print(n/10);
putchar(n%10+'0');
}bool SSS;
int n,m,Q;
int hsh[N],mi[N];
char s[N];
int lst[N],on[N],cnt=0;
inline int gethsh(int l,int r){return (hsh[r]-1ll*hsh[l-1]*mi[r-l+1]%Mod+Mod)%Mod;}
inline int suf(int l,int r,int x){
int L=1,R=min(l,x),res=0;
while(L<=R){
int mid=(L+R)>>1;
if(gethsh(l-mid+1,l)==gethsh(r-mid+1,r)) L=mid+1,res=mid;
else R=mid-1;
}return res;
}
inline int pre(int l,int r,int x){
int L=1,R=min(n-r+1,x),res=0;
while(L<=R){
int mid=(L+R)>>1;
if(gethsh(l,l+mid-1)==gethsh(r,r+mid-1)) L=mid+1,res=mid;
else R=mid-1;
}return res;
}
struct XXX{
int x;pii p;
}gg[N];int tot=0;
inline void solve(){
cnt=0;For(i,1,n) lst[i]=0;
For(i,1,n){
for(int j=i;j+i<=n;j+=i){
int lcp=pre(j,j+i,i),lcs=suf(j,j+i,i);
lcs=min(lcs,i);lcp=min(lcp,i);
int len=lcp+lcs-i;
if(lcp+lcs-1>=i){
int L=j-lcs+1,R=j-lcs+len;
if(tot&&gg[tot].x==i&&gg[tot].p.se-2*i+1>=L-1){
gg[tot].p.se=R+2*i-1;
}else{
gg[++tot]={i,{L,R+2*i-1}};
}
}
}
}
}
inline bool cmp(XXX a,XXX b){
if(a.p==b.p) return a.x<b.x;
if(a.p.fi==b.p.fi) return a.p.se>b.p.se;
return a.p.fi<b.p.fi;
}
inline bool cmb(XXX x,XXX y){
if(x.p.fi==y.p.fi) return x.x<y.x;
return x.p.fi<y.p.fi;
}
bool TTT;
signed main(){
cerr<<(&SSS-&TTT)/1024/1024<<"Mib"<<endl;
//_base=(_base<<64)/Mod;
// ios::sync_with_stdio(false);
// cin.tie(0); cout.tie(0);
// n=read(),Q=read();
mi[0]=1;
For(i,1,N-5) mi[i]=1ll*mi[i-1]*base%Mod;
// n=read(),Q=read();
scanf("%s",s+1);
n=strlen(s+1);
For(i,1,n){
hsh[i]=(1ll*hsh[i-1]*base+s[i])%Mod;
}
solve();
sort(gg+1,gg+tot+1,cmp);
int ans=0;cnt=0;
For(i,1,cnt)on[i]=0;
For(i,1,n) lst[i]=0; cnt=0;
For(i,1,tot){
if(gg[i].p==gg[i-1].p)continue;
gg[cnt++]=gg[i];
ans++;
}sort(gg,gg+cnt,cmb);
printf("%d\n",ans);
For(i,0,cnt-1) printf("%d %d %d\n",gg[i].p.fi,gg[i].p.se,gg[i].x);
#ifdef LOCAL
Debug("\nMy Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
return 0;
}
```
时间复杂度：$O(n\log^2 n)