题意
\(T\) 组数据，每组给出 \(n\) 个字符串，求一个最长字符串，满足其在每一个字符串都互不重叠地出现至少两次，输出其长度。
分析
既然是输出长度，很容易就能想到二分答案，二分可能的长度，对于一个已得的答案长度，比它小的长度一定也能满足，因为每一个该长度的串都能提取出更短的相同子串，因此二分的正确性便满足了。
对于每一个二分到的 \(mid\)，我们先在第一串中提取一个该长度的串，再在其后面寻找是否还有一个相同的串，如果有，再以同样的方法在其它串中寻找提取出的串，判断相同可以用哈希来处理，这样这道题就完成了。
代码
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long//unsigned long long 自然溢出
const int che=998244353;//用这个hash一般不会有啥问题
int cf[15005];
int T;
inline void read(int &res){
char c;
int f=1;
res=0;
c=getchar();
while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
while(c>=‘0‘&&c<=‘9‘)res=(res<<1)+(res<<3)+c-48,c=getchar();
res*=f;
}
int n;
int len[15];
char c[15][15005];
map<int,int>vis;
int mn;
//继续寻找第二份
int step2(int x,int pos,int mid,int kkk){//hash值，找2号起点，长度，第几个串
int sum=0,l=pos,r=pos+mid-1;
for(int i=l;i<=r;i++){
sum=sum*che+c[kkk][i];
}
if(sum==x)return 1;
while(r<len[kkk]){
sum-=c[kkk][l++]*cf[mid-1];
sum=sum*che+c[kkk][++r];
if(sum==x)return 1;
}
return 0;
}
int step3(int x,int mid){
for(int l=2;l<=n;l++){
int sum=0,ll=1,r=mid,bo=0;
for(int i=1;i<=mid;i++){
sum=sum*che+c[l][i];
}
while(r+mid<=len[l]){
if(sum==x){//找到第一个
if(step2(sum,r+1,mid,l)){
bo=2;
}
break;
//因为寻找的是两个不重叠的，所以第一次找到一个不管后面有没有都可以停止
}
sum-=c[l][ll++]*cf[mid-1];
sum=sum*che+c[l][++r];
}
if(bo!=2)return 0;
}
return 1;
}
int step1(int mid){//提取串
int sum=0,l=1,r=mid;
for(int i=1;i<=mid;i++){
sum=sum*che+c[1][i];
}
while(r+mid<=len[1]){
if(vis[sum]){
sum-=c[1][l++]*cf[mid-1];
sum=sum*che+c[1][++r];
continue;
}
vis[sum]=1;
int k=step2(sum,r+1,mid,1);
if(k){
k=step3(sum,mid);//开始在2~n-1中寻找相同子串
if(k)return 1;
}
sum-=c[1][l++]*cf[mid-1];
sum=sum*che+c[1][++r];
}
return 0;
}
signed main(){
read(T);
cf[0]=1;
for(int i=1;i<=15000;i++)cf[i]=cf[i-1]*che;
while(T--){
vis.clear();
read(n);
mn=15005;
for(int i=1;i<=n;i++){
scanf("%s",c[i]+1);
len[i]=strlen(c[i]+1);
mn=min(mn,len[i]);//二分右端点应为最短串的长度的一半
}
int l=1,r=mn/2,ans=0;
while(l<=r){
int mid=(l+r)>>1;
int k=step1(mid);
if(k){//该长度可行
ans=mid;
l=mid+1;//找更长
}
else r=mid-1;
}
cout<<ans<<endl;
}
return 0;
}