CF30E Tricky and Clever Password 题解

考虑先贪心中间的回文串 \(b\)，因为这即使影响了两边的字符串，也不会改变最终的总串长。所以先使用 manacher 跑出来每个位置的最长回文半径。

在考虑怎样找出最长的 \(a\) 和 \(a'\)。可以二分答案，设此时答案为 \(k\)，找出的 \(b\) 串为 \(s[l\dots r]\)，那么其合法的条件就是存在 \(i \in [1,l-k]\) 使得 \(lcp(s[i\dots n],rev(s)) \ge k\)。前缀查询 \(lcp\)，使用 Z 函数预处理前缀 \(\max\) 即可。

代码：

#include<bits/stdc++.h>
using namespace std;
inline void rd(){}
template<typename T,typename ...U>
inline void rd(T &x,U &...args){
	char ch=getchar();
	T f=1;x=0;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x*=f;rd(args...);          
} 
const int N=1e5+5;
char c[N],rv[N];
int n,p[N],z[N],zt[N],pr[N];
int ans,apos,mx=-1;
inline void manacher(){
	int now=0,mid=0;
	c[0]='~',c[n+1]='!';
	for(int i=1;i<=n;i++){
		if(i<=now)p[i]=min(p[2*mid-i],now-i+1);
		else p[i]=1;
		while(c[i+p[i]]==c[i-p[i]])++p[i];
		if(i+p[i]-1>=now)now=i+p[i]-1,mid=i;
	}
}
inline void ZAlgorithm(){
	int l=0,r=0;
	for(int i=2;i<=n;i++){
		if(i<=r)z[i]=min(z[i-l+1],r-i+1);
		else z[i]=0;
		while(i+z[i]<=n&&rv[i+z[i]]==rv[z[i]+1])++z[i];
		if(i+z[i]>r)r=i+z[i]-1,l=i;
	}
}
inline void zzz(){
	int l=0,r=0;
	for(int i=1;i<=n;i++){
		if(i<=r)zt[i]=min(z[i-l+1],r-i+1);
		else zt[i]=0;
		while(i+zt[i]<=n&&c[i+zt[i]]==rv[zt[i]+1])++zt[i];
		if(i+zt[i]>r)r=i+zt[i]-1,l=i;
	}
}
signed main(){
	scanf("%s",c+1);
	n=strlen(c+1);
	manacher();
	for(int i=1;i<=n;i++)rv[i]=c[n-i+1];
	ZAlgorithm();zzz();
	for(int i=1;i<=n;i++)pr[i]=max(pr[i-1],zt[i]);
	for(int i=1;i<=n;i++){
		int l=i-p[i]+1,r=i+p[i]-1;
		int L=0,R=min(n-r,l-1);
		while(L<=R){
			int k=(L+R)>>1;
			if(pr[l-k]>=k)L=k+1;
			else R=k-1;
		}
		if(R*2+p[i]*2-1>mx)ans=R,apos=i,mx=R*2+p[i]*2-1;
	}
	if(ans){
		printf("3\n");
		for(int i=1;i<=n;i++){
			if(zt[i]>=ans){
				printf("%d %d\n",i,ans);
				break;
			}
		} 
		printf("%d %d\n",apos-p[apos]+1,2*p[apos]-1);
		printf("%d %d\n",n-ans+1,ans);
	}else{
		printf("1\n%d %d\n",apos-p[apos]+1,2*p[apos]-1);
	}
	return 0;
}