本文共 3601 字，大约阅读时间需要 12 分钟。

给出一个串$s$,找出两个不相交的子串$a,b$($a$在前$b$在后)

满足$a+b$是一个回文串

考虑串$|a|>=|b|$怎么计算,因为如果$|a|<|b|$,只需要对反串也算一遍就好了

那么一定是$a=b+w$的形式,$w$是一个回文串

我们从回文串下手,枚举每个点$i$作为回文中心,最长的回文是$[l,r]$

那么让$[l,r]$作为$w$,考虑找到一个最小的$i$满足$[i,l-1]$是$[r+1,n]$的一个子串

正确性

如果不是最长的回文,比如变成$[l+1,r-1]$,那么最佳情况下$a$串长度减一,$b$串长度加一,总长度不变

如果回文变成$[l+1,r]$或$[l,r-1]$也不行,讨论一下就好了

考虑如何求最小的$i$满足$[i,l-1]$是$[r+1,n]$的子串

对$rev(S)$建立$SAM$,拿$S$的每个前缀放在$SAM$上匹配记节点为$pos[i]$

我们对$SAM$每个节点维护一个$m{i}_i$表示最小的$endpos$

这样我们就可以快速知道这个节点是否出现在$S$的$[r+1,n]$中了

因为在反串中出现最早,所以在原串$S$中最靠右

那么每次只需要把$pos[l-1]$向上跳,因为$mi$值父节点必定小于子节点,所以可以倍增快速跳

#include 
   
    using namespace std;#define fi first#define se secondconst int maxn = 4e5+10;typedef pair
    
     mp;mp p1,p2;int ans,n;char a[maxn];int zi[maxn][27],fa[maxn],id,las,l[maxn];int ed[maxn],mi[maxn],st[maxn][22];vector
     
      vec[maxn];void insert(int c,int index){
   	int p = las, np = ++id; las = id;	l[np] = l[p]+1; mi[np] = ed[np] = index;//最早出现的节点 	for( ; p&&zi[p][c]==0 ;p=fa[p] )	zi[p][c] = np;	if( p==0 )	fa[np] = 1;	else	{
   		int q = zi[p][c];		if( l[q]==l[p]+1 )	fa[np] = q;		else		{
   			int nq = ++id;			memcpy( zi[nq],zi[q],sizeof zi[nq] );			l[nq] = l[p]+1, fa[nq] = fa[q]; mi[nq] = mi[q], ed[nq] = ed[q];			fa[np] = fa[q] = nq;			for( ; p&&zi[p][c]==q;p=fa[p] )	zi[p][c] = nq;		}	}}void dfs(int u){
   	st[u][0] = fa[u];	for(int i=1;i<=20;i++)	st[u][i] = st[st[u][i-1]][i-1];	for( auto v:vec[u] )	{
   		dfs(v);		mi[u] = min( mi[u],mi[v] );		ed[u] = max( ed[u],ed[v] );	}}int pos[maxn],posl[maxn];//分别表示原串中每个前缀在自动机上的位置,和匹配长度 char P[maxn];int pal[maxn];void init(){
   	memset( st,0,sizeof st );	for(int i=0;i<=id;i++)	{
   		vec[i].clear();		memset( zi[i],0,sizeof zi[i] );		fa[i] = 0;	}	for(int i=0;i<=n+n+1;i++)		pos[i] = posl[i] = pal[i] = 0;	id = las = 1;}void work(){
   	init();	for(int i=1;i<=n;i++)	insert( a[i]-'a',i );	for(int i=2;i<=id;i++)	vec[fa[i]].push_back( i );	dfs(1);	for(int i=n,p=1,le=0;i>=1;i--)	{
   		int c = a[i]-'a';		if( zi[p][c] )	p = zi[p][c],le++;		else		{
   			while( p&&zi[p][c]==0 )	p = fa[p];			if( !p )	p = 1,le = 0;			else	le = l[p]+1, p = zi[p][c];			}		pos[i] = p;	 posl[i] = le;	}		int C=0,R=0,t=0;P[++t]='#';	for(int i=1;i<=n;i++) P[++t]=a[i],P[++t]='#';	for(int i=1;i<=t;i++)	{
   		if(i<=C+R) pal[i]=min(pal[2*C-i],C+R-i);else pal[i]=0;		while(i+pal[i]+1<=t&&i-pal[i]-1>=1&&			  P[i+pal[i]+1]==P[i-pal[i]-1]) pal[i]++;		if(i+pal[i]>=C+R) C=i,R=pal[i];	}	for(int i=1;i<=t;i++)		if(pal[i]>ans)			ans=pal[i],  p1=mp((i-pal[i]+1)/2,(i+pal[i]-1)/2),  p2=mp(-1,-1);	for(int i=1;i<=t;i++)	{
   		if(P[i]=='#'&&pal[i]==0) continue;		int zl=(i-pal[i]+1)/2,zr=(i+pal[i]-1)/2;		int x=pos[zr+1];//现在回文区间是[zl,zr]		for(int w=20;w>=0;w--)			if( mi[st[x][w]]>=zl )	x=st[x][w];		if( mi[x]>=zl ) x = st[x][0];		int vl=min( l[x],posl[zr+1] ),v=zr-zl+1+vl*2;		if(v>ans) ans=v,p1=mp( ed[x]-vl+1,ed[x] ),p2=mp(zl,zr+vl);	}		}int main(){
   	scanf("%s",a+1 ); n = strlen( a+1 );	reverse( a+1,a+1+n );	work();	if(p1.fi!=-1) p1.fi=n-p1.fi+1,p1.se=n-p1.se+1,swap(p1.fi,p1.se);	if(p2.fi!=-1) p2.fi=n-p2.fi+1,p2.se=n-p2.se+1,swap(p2.fi,p2.se);		reverse( a+1,a+1+n );	work();		if(p1.fi>p2.fi) swap(p1,p2);	printf("%d\n%d %d\n%d %d\n",ans,p1.fi,p1.se,p2.fi,p2.se);}
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/116062949 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！