思路：这题是论文里的最后一道练习题了，不过最后一题竟然挺水的。
因为求的是未反转或者反转后，最长公共子串。
刚开始还真不知道怎么构建连接成一个字符串，因为需要有反转嘛！
但是其实挺简单的，把未反转的和反转后的字符串都连起来，中间用未出现过的字符隔开就行了！然后未反转的和反转的在同一组。
二分枚举最长的公共前缀长度，然后统计看看这个最长的长度在不在所有的组里，如果在就符合……
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<bitset>
#define mem(a,b) memset(a,b,sizeof(a))
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define llson j<<1,l,mid
#define rrson j<<1|1,mid+1,r
#define INF 0x7fffffff
#define maxn 11010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
void radix(int *str,int *a,int *b,int n,int m)
{
static int count[maxn];
mem(count,0);
for(int i=0; i<n; i++) ++count[str[a[i]]];
for(int i=1; i<=m; i++) count[i]+=count[i-1];
for(int i=n-1; i>=0; i--) b[--count[str[a[i]]]]=a[i];
}
void suffix(int *str,int *sa,int n,int m) //倍增算法计算出后缀数组sa
{
static int rank[maxn],a[maxn],b[maxn];
for(int i=0; i<n; i++) rank[i]=i;
radix(str,rank,sa,n,m);
rank[sa[0]]=0;
for(int i=1; i<n; i++)
rank[sa[i]]=rank[sa[i-1]]+(str[sa[i]]!=str[sa[i-1]]);
for(int i=0; 1<<i<n; i++)
{
for(int j=0; j<n; j++)
{
a[j]=rank[j]+1;
b[j]=j+(1<<i)>=n?0:rank[j+(1<<i)]+1;
sa[j]=j;
}
radix(b,sa,rank,n,n);
radix(a,rank,sa,n,n);
rank[sa[0]]=0;
for(int j=1; j<n; j++)
rank[sa[j]]=rank[sa[j-1]]+(a[sa[j-1]]!=a[sa[j]]||b[sa[j-1]]!=b[sa[j]]);
}
}
void calcHeight(int *str,int *sa,int *h,int *rank,int n) //求出最长公共前缀数组h
{
int k=0;
h[0]=0;
for(int i=0; i<n; i++) rank[sa[i]]=i;
for(int i=0; i<n; i++)
{
k=k==0?0:k-1;
if(rank[i])
while(str[i+k]==str[sa[rank[i]-1]+k]) k++;
else k=0;
h[rank[i]]=k;
}
}
int a[maxn],sa[maxn],height[maxn],rank[maxn];
int v[maxn],vis[110],r,n,len,j;
char s[102];
bool judge(int m)
{
int tot=0;
mem(vis,0);vis[0]=1;//隔开的字符那组直接设置已经访问过
if(!vis[v[sa[0]]]) tot++,vis[v[sa[0]]]=1;
for(int i=1; i<len; i++)
{
if(height[i]<m)
{
mem(vis,0);tot=0;
vis[0]=1;
}
if(!vis[v[sa[i]]]) tot++,vis[v[sa[i]]]=1;
if(tot==n) return true;
}
return false;
}
int binary()
{
int ans=0,mid,l=0;
while(l<=r)
{
mid=(l+r)>>1;
if(judge(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
return ans;
}
int main()
{
//freopen("1.txt","r",stdin);
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
len=j=0;r=INF;
for(int i=1; i<=n; i++)
{
scanf("%s",s);
int len1=strlen(s);
if(r>len1) r=len1;//二分上限
for(int k=0; k<len1; k++)
a[len+k]=s[k]+150,v[len+k]=i;//v记录在哪个串中
a[len+len1]=++j;//字符串中间用没出现过的字符隔开
v[len+len1]=0;
len=len+len1+1;
for(int k=0; k<len1; k++)
a[len+k]=s[len1-k-1]+150,v[len+k]=i;//v记录在哪个串中
a[len+len1]=++j;//字符串中间用没出现过的字符隔开
v[len+len1]=0;
len=len+len1+1;
}
len--;
suffix(a,sa,len,500);
calcHeight(a,sa,height,rank,len);
printf("%d\n",binary());
}
return 0;
}
POJ 1226后缀数组：求出现或反转后出现在每个字符串中的最长子串,布布扣,bubuko.com
POJ 1226后缀数组：求出现或反转后出现在每个字符串中的最长子串
原文：http://blog.csdn.net/u011466175/article/details/38587419