考虑枚举回文中心，然后向两边扩展，当匹配到当前串的边界的时候，枚举下一个串接上。
这个过程可以通过记忆化搜索来完成，设：
$f[i][0]$表示对于$i$这个位置，$[i,串结尾]$等待匹配的最长回文子串。
$f[i][1]$表示对于$i$这个位置，$[串开头,i]$等待匹配的最长回文子串。
如果在转移的过程中发现两个串都已经匹配到了边界，或者转移有环，那么说明答案无限。
用后缀数组支持lcp的询问，时间复杂度$O(nL+Llog L)$。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=400010,M=105;
int n,m,i,j,k,x,y,st[M],en[M],from[N],f[N][2],v[N][2],vis[N][2],ans;char a[N],s[N];
namespace SA{
int n,rk[N],sa[N],height[N],tmp[N],cnt[N],Log[N],f[18][N];char s[N];
void build(int n,int m){
int i,j,k;n++;
for(i=0;i<n;i++)cnt[rk[i]=s[i]]++;
for(i=1;i<m;i++)cnt[i]+=cnt[i-1];
for(i=0;i<n;i++)sa[--cnt[rk[i]]]=i;
for(k=1;k<=n;k<<=1){
for(i=0;i<n;i++){
j=sa[i]-k;
if(j<0)j+=n;
tmp[cnt[rk[j]]++]=j;
}
sa[tmp[cnt[0]=0]]=j=0;
for(i=1;i<n;i++){
if(rk[tmp[i]]!=rk[tmp[i-1]]||rk[tmp[i]+k]!=rk[tmp[i-1]+k])cnt[++j]=i;
sa[tmp[i]]=j;
}
memcpy(rk,sa,n*sizeof(int));
memcpy(sa,tmp,n*sizeof(int));
if(j>=n-1)break;
}
for(j=rk[height[i=k=0]=0];i<n-1;i++,k++)
while(~k&&s[i]!=s[sa[j-1]+k])height[j]=k--,j=rk[sa[j]+1];
for(i=2;i<n;i++)Log[i]=Log[i>>1]+1;
for(i=1;i<n;i++)f[0][i]=height[i];
for(j=1;j<18;j++)for(i=1;i+(1<<j)-1<n;i++)f[j][i]=min(f[j-1][i],f[j-1][i+(1<<(j-1))]);
}
inline int ask(int x,int y){
int k=Log[y-x+1];
return min(f[k][x],f[k][y-(1<<k)+1]);
}
inline int lcp(int x,int y){
if(x==y)return N;
x=rk[x],y=rk[y];
if(x>y)swap(x,y);
return ask(x+1,y);
}
}
inline int query(int x,int y){
return min(SA::lcp(x,m-1-y),min(en[from[x]]-x,y-st[from[y]])+1);
}
void getinf(){
puts("Infinity");
exit(0);
}
int dfs(int u,int p){
if(vis[u][p])getinf();
if(v[u][p])return f[u][p];
v[u][p]=vis[u][p]=1;
int&ret=f[u][p];
if(!p){
for(int i=1;i<=n;i++){
int k=query(u,en[i]);
int x=u+k-1,y=en[i]-k+1;
if(x<en[from[u]]&&y>st[i])ret=max(ret,k*2);
else if(x==en[from[u]]&&y==st[i])getinf();
else if(x==en[from[u]])ret=max(ret,k*2+dfs(y-1,1));
else ret=max(ret,k*2+dfs(x+1,0));
}
}else{
for(int i=1;i<=n;i++){
int k=query(st[i],u);
int x=u-k+1,y=st[i]+k-1;
if(x>st[from[u]]&&y<en[i])ret=max(ret,k*2);
else if(x==st[from[u]]&&y==en[i])getinf();
else if(x==st[from[u]])ret=max(ret,k*2+dfs(y+1,0));
else ret=max(ret,k*2+dfs(x-1,1));
}
}
vis[u][p]=0;
return ret;
}
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%s",a);
st[i]=m;
for(j=0;a[j];j++)from[m]=i,s[m++]=a[j];
en[i]=m-1;
}
m<<=1;
for(i=0,j=m-1;i<j;i++,j--)s[j]=s[i],from[j]=from[i];
for(SA::n=m,i=0;i<m;i++)SA::s[i]=s[i];
SA::build(m,128);
for(i=1;i<=n;i++)ans=max(ans,max(dfs(st[i],0),dfs(en[i],1)));
for(i=1;i<=n;i++){
for(j=st[i];j<=en[i];j++){
k=query(j,j);
x=j-k+1,y=j+k-1;
if(x>st[i]&&y<en[i])ans=max(ans,k*2-1);
else if(x==st[i]&&y==en[i])getinf();
else if(x==st[i])ans=max(ans,k*2-1+dfs(y+1,0));
else ans=max(ans,k*2-1+dfs(x-1,1));
}
for(j=st[i];j<en[i];j++){
k=query(j+1,j);
x=j-k+1,y=j+k;
if(x>st[i]&&y<en[i])ans=max(ans,k*2);
else if(x==st[i]&&y==en[i])getinf();
else if(x==st[i])ans=max(ans,k*2+dfs(y+1,0));
else ans=max(ans,k*2+dfs(x-1,1));
}
}
return printf("%d",ans),0;
}