题目
Substrings Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 14254 Accepted: 5064 Description
You are given a number of case-sensitive strings of alphabetic characters, find the largest string X, such that either X, or its inverse can be found as a substring of any of the given strings. Input
The first line of the input contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains a single integer n (1 <= n <= 100), the number of given strings, followed by n lines, each representing one string of minimum length 1 and maximum length 100. There is no extra white space before and after a string. Output
There should be one line per test case containing the length of the largest string found. Sample Input
2 3 ABCD BCDFF BRCD 2 rose orchid Sample Output
2 2
题目大意
给一坨字符串，求一个最长的串的长度，使得这个串在每一个串或这个串倒过来之后是其子串（连续的）
做法
首先把每一个串以及其倒过来之后的串连接在一起，然后用一个数组来记录每一个位置属于哪一个字符串，然后二分求可行性就可以了
贴代码
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int ma=
25005;
int sa[ma],height[ma],rank[ma],x[ma],y[ma],buc[ma],bi[ma],go[ma];
char s[ma],s1[ma];
bool bz[ma];
int i,j,k,l,r,n,t,len,now,m,p,o,t1,t2,ans,zo,mi,mid;
void gesa(){
m=
96+
26;
memset(y,
0,
sizeof(y));
fo(i,
0,len-
1) x[i]=s[i];
fo(i,
1,m) buc[i]=
0;
fo(i,
0,len-
1) buc[x[i]]++;
fo(i,
1,m) buc[i]+=buc[i-
1];
fo(i,
0,len-
1) sa[buc[x[i]]--]=i;
for(k=
1;k<len;k=k*
2){
p=
0;
fo(i,len-k,len-
1) y[++p]=i;
fo(i,
1,len)
if (sa[i]>=k) y[++p]=sa[i]-k;
fo(i,
1,m) buc[i]=
0;
fo(i,
0,len-
1) buc[x[i]]++;
fo(i,
1,m) buc[i]+=buc[i-
1];
for(i=len;i>=
1;i--) sa[buc[x[y[i]]]--]=y[i];
fo(i,
0,len-
1) y[i]=x[i];
x[sa[
1]]=
1;
fo(i,
2,len){
if (y[sa[i]]==y[sa[i-
1]] && y[sa[i]+k]==y[sa[i-
1]+k]) x[sa[i]]=x[sa[i-
1]];
else x[sa[i]]=x[sa[i-
1]]+
1;
}
m=x[sa[len]];
if (m>=len)
break;
}
fo(i,
1,len) rank[sa[i]]=i;
}
void gehei(){
k=
0;
fo(i,
0,len-
1){
if (rank[i]==
1){
height[rank[i]]=
0;
continue;
}
if (k) k--;
t1=i+k; t2=sa[rank[i]-
1]+k;
while (t1<len && t2<len){
if (s[t1]==
'#' || s[t2]==
'#')
break;
if (s[t1]!=s[t2])
break;
k++; t1++; t2++;
}
height[rank[i]]=k;
}
}
bool geans(
int k){
now=
0;
memset(bz,
false,
sizeof(bz));
fo(i,
1,len)
if (s[sa[i]]!=
'#')
{
if (height[i]<k){
fo(j,
1,now) bz[go[j]]=
false;
now=
1;
go[
1]=bi[sa[i]];
bz[bi[sa[i]]]=
true;
continue;
}
if (bz[bi[sa[i]]]==
false){
go[++now]=bi[sa[i]];
bz[bi[sa[i]]]=
true;
}
if (now==zo)
return true;
}
return false;
}
void getwo(){
l=
0;
r=mi;
while (l<r){
mid=(l+r)/
2;
if (geans(mid)) l=mid+
1;
else r=mid;
}
if (geans(l)==
false) l--;
printf(
"%d\n",l);
}
int main(){
scanf(
"%d",&t);
fo(o,
1,t){
scanf(
"%d",&n);
now=
0;
zo=
0;
mi=ma;
fo(i,
1,n){
scanf(
"%s",&s1);
len=
strlen(s1);
mi=min(len,mi);
zo++;
fo(j,
0,len-
1)
{
s[now]=s1[j];
bi[now++]=zo;
}
s[now++]=
'#';
for(j=len-
1;j>=
0;j--)
{
s[now]=s1[j];
bi[now++]=zo;
}
s[now++]=
'#';
}
len=now;
gesa();
gehei();
getwo();
}
return 0;
}
