Substrings
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 10998 | Accepted: 3824 |
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
题意：给定一些字符串，求出现或者翻转后出现在每一个串中的最长子串。
解题思路：将每一个串以及翻转后的串都连起来，中间用不相同且未出现过的字符分割开，然后二分长度，根据后缀数组height值分组判定。
代码：
/* ***********************************************
Author :xianxingwuguan
Created Time :2014-2-1 2:59:27
File Name :1.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int maxn=30100;
const double pi =acos(-1.0);
const double eps =1e-8;
int height[maxn],sa[maxn],rank[maxn],c[maxn],t1[maxn],t2[maxn];
void da(int *str,int n,int m)
{
int i,j,k,p,*x=t1,*y=t2;
for(i=0;i<m;i++)c[i]=0;
for(i=0;i<n;i++)c[x[i]=str[i]]++;
for(i=1;i<m;i++)c[i]+=c[i-1];
for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
for(k=1;k<=n;k<<=1)
{
p=0;
for(i=n-k;i<n;i++)y[p++]=i;
for(i=0;i<n;i++)if(sa[i]>=k)y[p++]=sa[i]-k;
for(i=0;i<m;i++)c[i]=0;
for(i=0;i<n;i++)c[x[y[i]]]++;
for(i=1;i<m;i++)c[i]+=c[i-1];
for(i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];
swap(x,y);
p=1;x[sa[0]]=0;
for(i=1;i<n;i++)
x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p-1:p++;
if(p>=n)break;
m=p;
}
}
void calheight(int *str,int n)
{
int i,j,k=0;
for(i=0;i<=n;i++)rank[sa[i]]=i;
for(i=0;i<n;i++)
{
if(k)k--;
j=sa[rank[i]-1];
while(str[i+k]==str[j+k])k++;
height[rank[i]]=k;
}
// printf("sa:");for(i=0;i<=n;i++)printf("%d ",sa[i]);puts("");
// printf("rank:");for(i=0;i<=n;i++)printf("%d ",rank[i]);puts("");
// printf("height:");for(i=0;i<=n;i++)printf("%d ",height[i]);puts("");
}
int str[maxn],loc[maxn],vis[maxn];
char ss[maxn];
int n;
bool check(int mid,int len)
{
int i,j,tot;
tot=0;
memset(vis,0,sizeof(vis));
for(i=2;i<=len;i++)
{
if(height[i]<mid)
{
memset(vis,0,sizeof(vis));
tot=0;
}
else
{
if(!vis[loc[sa[i-1]]])
{
vis[loc[sa[i-1]]]=1;
tot++;
}
if(!vis[loc[sa[i]]]){
vis[loc[sa[i]]]=1;
tot++;
}
if(tot==n)return 1;
}
}
return 0;
}
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
int T,i,j;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int len=0;
int ff=200;
int left=0,right;
for(i=1;i<=n;i++)
{
scanf("%s",ss);
int cnt=strlen(ss);
right=cnt;
for(j=0;j<cnt;j++)str[len]=ss[j]+500,loc[len++]=i;
str[len]=ff;
loc[len++]=ff++;
for(j=cnt-1;j>=0;j--)str[len]=ss[j]+500,loc[len++]=i;
str[len]=ff;
loc[len++]=ff++;
}
str[len]=0;
// cout<<"len="<<len<<endl;
da(str,len+1,1000);
calheight(str,len);
while(left<right)
{
int mid=(left+right+1)>>1;
if(check(mid,len))left=mid;
else right=mid-1;
}
printf("%d\n",left);
}
return 0;
}