WA on #46求助

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;
const int Base=1145141;
const int Mod=998244353;
int n;
int len[N],d[N];
int pre[N],suf[N],PowBase[N];
int Log[N],f[N][18],g[N][18];
char a[N>>1];
vector<pair<int,int> > vec;
int getpre(int l,int r){
	return (pre[r]-pre[l-1]*PowBase[r-l+1]%Mod+Mod)%Mod;
}
int getsuf(int l,int r){
	return (suf[l]-suf[r+1]*PowBase[r-l+1]%Mod+Mod)%Mod;
}
void init(){
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			if(f[i][j-1]>f[i+(1<<j-1)][j-1]) f[i][j]=f[i][j-1],g[i][j]=g[i][j-1];
			else f[i][j]=f[i+(1<<j-1)][j-1],g[i][j]=g[i+(1<<j-1)][j-1];
		}
	}
}
int query(int l,int r){
	int _Log=Log[r-l+1];
	return max(f[l][_Log],f[r-(1<<_Log)+1][_Log]);
}
int pos(int l,int r){
	int _Log=Log[r-l+1];
	if(f[l][_Log]>f[r-(1<<_Log)+1][_Log]) return g[l][_Log];
	else return g[r-(1<<_Log)+1][_Log];
}
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%s",a+1);
	n=strlen(a+1);
	Log[0]=-1;
	for(int i=1;i<=n;i++) Log[i]=Log[i>>1]+1;
	PowBase[0]=1;
	for(int i=1;i<=n;i++) PowBase[i]=PowBase[i-1]*Base%Mod;
	for(int i=1;i<=n;i++) pre[i]=(pre[i-1]*Base%Mod+a[i]-'a')%Mod;
	for(int i=n;i>=1;i--) suf[i]=(suf[i+1]*Base%Mod+a[i]-'a')%Mod;
	for(int i=1;i<=n;i++){
		int l=1,r=(n-i)/2,x=0;
		while(l<=r){
			int mid=(l+r)>>1;
			if(getpre(i,i+mid-1)==getsuf(n-mid+1,n)) x=mid,l=mid+1;
			else r=mid-1;
		}
		len[i]=x;
	}
	int l=0,r=0;
	for(int i=1;i<=n;i++) d[i]=1;
	for(int i=1;i<=n;i++){
		if(i<=r) d[i]=min(d[l+r-i],r-i+1);
		while(i+d[i]<=n&&i-d[i]>=1&&a[i+d[i]]==a[i-d[i]]) d[i]++;
		if(i+d[i]-1>r){
			l=i-d[i]+1;
			r=i+d[i]-1;
		}
		f[i][0]=d[i];
		g[i][0]=i;
	}
	init();
	int ans=0;
	for(int i=1;i<=n;i++){
		int L=i+len[i],R=n-len[i];
		int l=1,r=(R-L)/2+1,x=0;
		while(l<=r){
			int mid=(l+r)>>1;
			if(query(L+mid-1,R-mid+1)>=mid) x=mid,l=mid+1;
			else r=mid-1;
		}
		if(2*len[i]+2*x-1>ans){
			vec.clear();
			ans=2*len[i]+2*x-1;
			if(!len[i]) vec.push_back(make_pair(pos(L+x-1,R-x+1)-x+1,2*x-1));
			else{
				vec.push_back(make_pair(i,len[i]));
				vec.push_back(make_pair(pos(L+x-1,R-x+1)-x+1,2*x-1));
				vec.push_back(make_pair(n-len[i]+1,len[i]));
			}
		} 
	}
	printf("%lld\n",(int)vec.size());
	for(int i=0;i<vec.size();i++) printf("%lld %lld\n",vec[i].first,vec[i].second);
	return 0;
}