Runs 求卡常

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
const int N=1e6+10;
int sa[N],rk[2][N],old[N],cnt[N],id[N],p,he[N],st[N][22][2];
inline bool cmp(int x,int y,int w){
	return old[x]==old[y]&&old[x+w]==old[y+w];
}
inline void get(string s,int n,int fl){
	int k=0;
	for(int i=1;i<=n;i++){
		if(rk[fl][i]==0)continue;
		if(k)k--;
		while(s[i+k]==s[sa[rk[fl][i]-1]+k])k++;
		he[rk[fl][i]]=k;
		st[rk[fl][i]][0][fl]=k;
	}
	for(int i=1;i<=20;i++){
		for(int j=1;j+(1<<(i-1))<=n;j++){
			st[j][i][fl]=min(st[j][i-1][fl],st[j+(1<<(i-1))][i-1][fl]);
		}
	}
}
inline int lcp(int x,int y,int n,int fl){
	if(x<1||y>n)return 0;
	x=rk[fl][x],y=rk[fl][y];
	if(x>y)swap(x,y);
	x++;
	int s=__lg(y-x+1);
	return min(st[x][s][fl],st[y-(1<<s)+1][s][fl]);
}
inline void SA(string s,int n,int m,int fl){
	memset(cnt,0,sizeof(cnt));
	for(int i=1;i<=n;i++)++cnt[rk[fl][i]=s[i]];
	for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1]; 
	for(int i=n;i>=1;i--)sa[cnt[rk[fl][i]]--]=i;
	for(int w=1;;w<<=1,m=p){
		p=0;
		for(int i=n;i>n-w;i--)id[++p]=i;
		for(int i=1;i<=n;i++){
			if(sa[i]>w)id[++p]=sa[i]-w;
		}
		memset(cnt,0,sizeof(cnt));
		for(int i=1;i<=n;i++)++cnt[rk[fl][id[i]]];
		for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
		for(int i=n;i>=1;i--)sa[cnt[rk[fl][id[i]]]--]=id[i];
		memcpy(old+1,rk[fl]+1,n*sizeof(int));
		p=0;
		for(int i=1;i<=n;i++)rk[fl][sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;
		if(p==n)break;
	}
}
gp_hash_table<long long,int> h;
pair<long long,int> C[2*N];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin>>s;
	int n=s.size(),m=127;
	SA(' '+s,n,m,0);
	get(' '+s,n,0);
	reverse(s.begin(),s.end());
	SA(' '+s,n,m,1);
	get(' '+s,n,1);
	for(int p=1;p*2<=n;p++){
		for(int i=1;i*p<=n;i++){
			int l=(i-1)*p+1,r=i*p;
			int edd=r+lcp(l,r+1,n,0);
			int stt=l-lcp(n-r+1,n-l+2,n,1);
			long long to=1ll*stt*(n+1)+edd;
			if(p*2>edd-stt+1||h.find(to)!=h.end())continue;
			h[to]=p;
		}
	}
	cout<<h.size()<<'\n';
	int cc=0;
	for(auto [x,y]:h){
		C[++cc]={x,y};
	}
	sort(C+1,C+cc+1);
	for(int i=1;i<=cc;i++){
		auto [x,y]=C[i];
		int l=x/(n+1),r=x%(n+1);
		cout<<l<<' '<<r<<' '<<y<<'\n';
	}
	return 0;
}