  /**//*
 【題目】給定n個(gè)串，求一個(gè)最大子串長(zhǎng)度，使得它或者它的逆向串在每個(gè)串中出現(xiàn)。
【分析】先把每個(gè)串倒序復(fù)制一遍，然后二分，分組。只要每個(gè)組里面有N個(gè)不同的串就滿足條件
 */
 #include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 20000+5
#define min(a,b) ((a)<(b)?(a):(b))
char s[maxn],str[maxn];
int sa[maxn],h[maxn],height[maxn],rank[maxn];
int k,n;
int minlen;
int m;
int belong[maxn];
bool cmp1(const int & a,const int & b)
 {
return (s[a]<s[b]);
}
bool cmp2(const int & a,const int & b)
{
return (rank[a]<rank[b] || (rank[a]==rank[b]&&
(a+k<n?rank[a+k]:-1)<(b+k<n?rank[b+k]:-1)));
}
void suffixArray()
{
int i,j;
for(i=0;i<n;i++)
sa[i]=i;
sort(sa,sa+n,cmp1);
for(i=0;i<n;i++)
  {
if(i==0||s[sa[i]]!=s[sa[i-1]])
rank[sa[i]]=i;
else rank[sa[i]]=rank[sa[i-1]];
 }
for(k=1;k<n;k*=2)
{
sort(sa,sa+n,cmp2);
for(i=0;i<n;i++)
{
if( i==0 || (cmp2(sa[i],sa[i-1])||cmp2(sa[i-1],sa[i])) )
h[sa[i]]=i;
else h[sa[i]]=h[sa[i-1]];
}
memcpy(rank, h, n * sizeof(int));
}
height[0] = 0;
for(i = 0, j = 0; i < n; i++)
{
if(rank[i]>0)
{
while(s[sa[rank[i] - 1] + j] == s[i + j])
j++;
height[rank[i]] = j;
if(j > 0) j--;
}
}
}
bool ok(int len)
{
int count=0;
bool visit[105]={0};
for(int i=1;i<n;i++)
{
if(height[i]<len)
{
if(count>0)
{
count=0;
memset(visit,0,sizeof(visit));
}
}
else
{
if(!visit[belong[sa[i-1]]])
{
visit[belong[sa[i-1]]]=1;
count++;
}
if(!visit[belong[sa[i]]])
{
visit[belong[sa[i]]]=1;
count++;
}
if(count>=m)
return 1;
}
}
return 0;
}
int binarySearch()
{
int l=0,r=minlen;
int mid;
while(l<r)
{
mid=(l+r+1)>>1;
if(ok(mid))
l=mid;
else r=mid-1;
}
return l;
}
char* strrev(char * ps)
{
int t=strlen(ps);
char tmp;
for(int i=0;i<t/2;i++)
{
tmp=ps[i];
ps[i]=ps[t-1-i];
ps[t-1-i]=tmp;
}
return ps;
}
int main()
{
int t,tmp,j;
scanf("%d", &t);
while(t--)
{
scanf("%d",&m);
n=0;
minlen=INT_MAX;
for(int i=0;i<m;i++)
{
scanf("%s",str);
tmp=strlen(str);
if(tmp<minlen)
minlen=tmp;
j=n;
strcpy(s+n,str);
n+=tmp;
s[n++]='z'+i+1;
strrev(str);
strcpy(s+n,str);
n+=tmp;
s[n++]='z'+i+1;
for(;j<n;j++)
belong[j]=i;
}
s[n]='$';
suffixArray();
printf("%d\n",binarySearch());
}
return 0;
}
|