引用罗穗骞论文中的话：
先将n 个字符串连起来，中间用不相同的且没有出现在字符串中的字符隔开，求后缀数组。然后二分答案，再将后缀分组。判断的时候，要看是否有一组后缀在每个原来的字符串中至少出现两次，并且在每个原来的字符串中，后缀的起始位置的最大值与最小值之差是否不小于当前答案（判断能否做到不重叠，如果题目中没有不重叠的要求，那么不用做此判断）。这个做法的时间复杂度为O(nlogn)。
二分枚举长度，对每个长度遍历height[]数组，将height[]数组分块，每个块内任意两串的lcp均大于等于m，则这些串的前m位相同。
使用mi[], mx数组存储每个串匹配成功时下标最大与最小值，当mx[tp] - mi[tp] >= m 时说明找到两个串且不重叠。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
const int N = 1100000; int sa[N], rank[N], height[N]; int mi[15], mx[15]; char tp[100008];
int str[N];
int vis[15];
int hs[N]; int wa[N],wb[N],wv[N],ws1[N];
int cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int *r,int *sa,int n,int m)
{
int i,j,p,*x=wa,*y=wb,*t;
for(i=0;i<m;i++) ws1[i]=0;
for(i=0;i<n;i++) ws1[x[i]=r[i]]++;
for(i=1;i<m;i++) ws1[i]+=ws1[i-1];
for(i=n-1;i>=0;i--) sa[--ws1[x[i]]]=i;
for(j=1,p=1;p<n;j*=2,m=p)
{
for(p=0,i=n-j;i<n;i++) y[p++]=i;
for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
for(i=0;i<n;i++) wv[i]=x[y[i]];
for(i=0;i<m;i++) ws1[i]=0;
for(i=0;i<n;i++) ws1[wv[i]]++;
for(i=1;i<m;i++) ws1[i]+=ws1[i-1];
for(i=n-1;i>=0;i--) sa[--ws1[wv[i]]]=y[i];
for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
return;
}
void calheight(int *r,int *sa,int n)
{
int i,j,k=0;
for(i=1;i<=n;i++) rank[sa[i]]=i;
for(i=0;i<n;height[rank[i++]]=k)
for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
return;
} bool check(int n, int m, int num){
memset(vis, 0, sizeof(vis));
memset(mi, 0x3F, sizeof(mi));
memset(mx, 0, sizeof(mx));
int cnt = 0;
for(int i = 1; i <= n; i++){
if(height[i] >= m){
int tp = hs[sa[i]];
mi[tp] = min(mi[tp], sa[i]);
mx[tp] = max(mx[tp], sa[i]);
if(mx[tp] - mi[tp] >= m){
if(!vis[tp]){
cnt++;
vis[tp] = 1;
}
} tp = hs[sa[i - 1]];
mi[tp] = min(mi[tp], sa[i - 1]);
mx[tp] = max(mx[tp], sa[i - 1]);
if(mx[tp] - mi[tp] >= m){
if(!vis[tp]){
cnt++;
vis[tp] = 1;
}
}
}else{
if(cnt == num){
return true;
}
memset(vis, 0, sizeof(vis));
memset(mi, 0x3F, sizeof(mi));
memset(mx, 0, sizeof(mx));
cnt = 0;
}
}
return false;
} int main(){
int t;
cin>>t;
while(t--){
int n = 0;
int mini = 100000000;
scanf("%d", &n);
int len = 0;
for(int t = 0 ; t < n; t++){
scanf("%s", tp);
int m = strlen(tp);
mini = min(mini, m);
for(int i = len , j = 0; j < m; i++, j++){
str[i] = tp[j];
hs[i] = t;
}
len += m + 1;
if(t != n - 1){
str[len - 1] = t + 130;
}
}
len--;
str[len] = 0;
da(str, sa, len + 1, 256);
calheight(str, sa, len);
int ans = 0;
int l =1, r = mini/ 2;
while(l <= r){
int m = (l + r)>>1;
if(check(len, m, n)){
l = m + 1;
ans = m;
}else{
r = m - 1;
}
}
printf("%d\n", ans); }
return 0;
}