- 给定一个字符串集合，你可以按任意的顺序选出其中任意个串任意多次拼成一个新的字符串，求新串可能的最长回文子串长度。如果可能达到无穷大输出(Infinity)。
- (nle100,Lle10^3)或(n=1,Lle10^5)
关于(n=1)的部分
其实很简单，只要分别求出两倍原串和三倍原串中的最长回文子串长度，如果一样就是答案，否则输出(Infinity)。
直接枚举对称轴二分+哈希即可。
回文串的套路动态规划
本以为是道字符串题一直没啥想法，看了题解发现实际上往动态规划的方向去想似乎更简单。
考虑一个非常暴力的(DP)，就是设(f_{i,x,j,y})表示以(s[i])的第(x)个字符为左端点，(s[j])的第(y)个字符为右端点时的最大长度。
转移时，如果两个字符串都不在端点上，只能继续使用这两个字符串。而如果两个都在端点上，那么答案为(Infinity)。再不然，恰有一个字符串在端点上时，我们可以把在端点上的这个字符串替换掉，直接暴力枚举用哪个字符串来替换即可。
然后就发现一个很基本的优化，就是两个字符串都不在端点上的转移唯一，似乎状态开着有些浪费。
因此我们直接设(f_{i,x,0/1})表示以(s[i])的第(x)个字符为一个端点（(0/1)记录是哪个端点）时的最大长度，转移就枚举添加的一个字符串，直接哈希+二分求出能匹配的最大长度。
如果两个都不在端点上，无法继续转移。如果一个在端点上，那么就产生了一个新状态。如果两个都在端点上，那么答案为(Infinity)。
(SPFA)转移(DP)
考虑直接转移的话，状态的转移顺序很难确定，而且甚至可能会出现环（出现环时答案为(Infinity)）
我们可以直接把这些状态转移看作一张图，那么直接利用(SPFA)跑一遍最长度即可。
如果出现了环，那么答案可能会无限增大，因此我们可以设置当答案大于(10^6)的时候就直接输出(Infinity)。
复杂度虽然有点奇怪，但显然跑不满。
代码：(O(kn^2LlogL))（(k)为(SPFA)系数）
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100
#define M 1000
#define MAX 100000
#define PS (2*N*(M+1))
#define P(x,y,z) (((x)-1)*(M+1)*2+(y)*2+(z))
#define Gmax(x,y) (x<(y)&&(x=(y)))
using namespace std;
int n,l[N+5],dis[PS+5],IQ[PS+5];char s[N+5][M+5];queue<int> q;
struct Hash
{
#define ull unsigned long long
#define CU Con ull&
ull x,y;I Hash() {x=y=0;}I Hash(CU a) {x=y=a;}I Hash(CU a,CU b):x(a),y(b){}
I Hash operator + (Con Hash& o) Con {return Hash(x+o.x,y+o.y);}
I Hash operator - (Con Hash& o) Con {return Hash(x-o.x,y-o.y);}
I Hash operator * (Con Hash& o) Con {return Hash(x*o.x,y*o.y);}
I bool operator == (Con Hash& o) Con {return x==o.x&&y==o.y;}
}pre[N+5][M+5],suf[N+5][M+5],sd(302627441,11743207),pw[M+5];
namespace For_1
{
int l;char s[3*MAX+5];Hash pre[3*MAX+5],suf[3*MAX+5],pw[3*MAX+5];
I int Calc(CI x,CI y)//二分
{
RI L=0,R=min(x,l-y),mid;W(L^R) mid=L+R+1>>1,
suf[x-mid]-suf[x]*pw[mid]==pre[y+mid]-pre[y]*pw[mid]?L=mid:R=mid-1;return L;
}
I void Solve()
{
RI i,t=0;for(scanf("%s",s+1),l=strlen(s+1),pw[0]=i=1;i<=3*l;++i) pw[i]=pw[i-1]*sd;
for(i=1;i<=l;++i) s[l+i]=s[2*l+i]=s[i];//复制
for(i=1;i<=3*l;++i) pre[i]=pre[i-1]*sd+s[i];for(i=3*l;i;--i) suf[i]=suf[i+1]*sd+s[i];//预处理哈希数组
for(l*=2,i=1;i<=l;++i) Gmax(t,2*Calc(i,i)+1);for(i=1;i^l;++i) s[i]==s[i+1]&&Gmax(t,2*Calc(i,i+1)+2);//两倍原串的答案
for(l*=1.5,i=1;i<=l;++i) if(2*Calc(i,i)+1>t) return (void)puts("Infinity");//如果三倍原串答案更大
for(i=1;i^l;++i) if(s[i]==s[i+1]&&2*Calc(i,i+1)+2>t) return (void)puts("Infinity");printf("%d
",t);//如果三倍原串答案更大；输出答案
}
}
I int Calc(CI i,CI x,CI j,CI y)//二分
{
RI L=0,R=min(x,l[j]-y),mid;W(L^R) mid=L+R+1>>1,
suf[i][x-mid]-suf[i][x]*pw[mid]==pre[j][y+mid]-pre[j][y]*pw[mid]?L=mid:R=mid-1;return L;
}
int main()
{
RI i,j,k;if(scanf("%d",&n),n==1) return For_1::Solve(),0;//特判n=1
for(pw[0]=i=1;i<=M;++i) pw[i]=pw[i-1]*sd;for(i=1;i<=n;++i) scanf("%s",s[i]+1),l[i]=strlen(s[i]+1);
for(i=1;i<=n;++i) for(j=1;j<=l[i];++j) pre[i][j]=pre[i][j-1]*sd+s[i][j];//预处理前缀哈希
for(i=1;i<=n;++i) for(j=l[i];j;--j) suf[i][j]=suf[i][j+1]*sd+s[i][j];//预处理后缀哈希
#define F5(x,v) (dis[x]<v&&(dis[x]=v,!IQ[x]&&(q.push(x),IQ[x]=1)))//用v更新x的距离
#define Init(x,y)
{
if(d=Calc(i,x,i,y),Gmax(ans,2*d+(y-x+1)),x-d==1&&y+d==l[i]) return puts("Infinity"),0;
x-d==1&&F5(P(i,y+d,0),2*d+(y-x+1)),y+d==l[i]&&F5(P(i,x-d,1),2*d+(y-x+1));
}
RI d,ans=0;for(i=1;i<=n;++i) q.push(P(i,0,0)),q.push(P(i,l[i]+1,1)),IQ[P(i,0,0)]=IQ[P(i,l[i]+1,1)]=1;//把所有空串加入状态
for(i=1;i<=n;++i) for(j=1;j<=l[i];++j) Init(j,j);//奇数回文串
for(i=1;i<=n;++i) for(j=1;j^l[i];++j) if(s[i][j]==s[i][j+1]) Init(j,j+1);//偶数回文串
RI id,x;W(!q.empty())//SPFA
{
if(IQ[k=q.front()]=0,q.pop(),id=(k>>1)/(M+1)+1,x=(k>>1)%(M+1),dis[k]>1e6) return puts("Infinity"),0;//出现环
for(i=1;i<=n;++i) if(k&1)//枚举一个串放右边
{
if(!(d=Calc(id,x,i,0))) continue;if(x-d==1&&d==l[i]) return puts("Infinity"),0;
Gmax(ans,dis[k]+2*d),x-d==1&&F5(P(i,d,0),dis[k]+2*d),d==l[i]&&F5(P(id,x-d,1),dis[k]+2*d);
}
else//枚举一个串放左边
{
if(!(d=Calc(i,l[i]+1,id,x))) continue;if(d==l[i]&&x+d==l[id]) return puts("Infinity"),0;
Gmax(ans,dis[k]+2*d),d==l[i]&&F5(P(id,x+d,0),dis[k]+2*d),x+d==l[id]&&F5(P(i,l[i]+1-d,1),dis[k]+2*d);
}
}return printf("%d
",ans),0;
}