/*初看这题 以为是传统意义上的最长重复子串.其实不然,看例子就明白*/
接触这题后才开始看Suffix_array的资料.一篇论文,里面谈到如何使用O(nlogn)的方法构造后缀数组SA.并且用0(nlongn)的方法构造height数组. 点击下载后缀数组论文
以下代码写的有点粗糙..排序上其实可以优化很多.我只使用sort()进行排序 惭愧.....
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define N 200000
int sa[N];
int rank[N];
int lrank[N],h[N],height[N];
int k;
char str[50005];
bool cmpchar(const int& a,const int& b)
{
return str[a]<str[b];
}
bool cmprank(const int&a ,const int&b)
{
return rank[a]<rank[b]||(rank[a]==rank[b]&&rank[a+k]<rank[b+k]);
}
bool equ(const int& a,const int& b)
{
return lrank[a]==lrank[b]&&lrank[a+k]==lrank[b+k];
}
void createSA(int len)
{
int i=0;
for(i=0;i<len;i++)
sa[i]=i;
sort(sa,sa+len,cmpchar);
//SA(1) 每个后缀的首字母有关。这里其实可以采用计数排序
//rank(1) 根据SA(1)求得的排名数组
for(rank[sa[0]]=0,i=1;i<len;i++)
{
rank[sa[i]]=rank[sa[i-1]];
if(str[sa[i]]!=str[sa[i-1]])
rank[sa[i]]++;
}
//在SA(1)基础上扩展到SA(2^k) ->(2^k>=len)
for(k=1;k<len;k*=2)
{
//根据Rank(k)数组求SA(2k)
//Suffix(i)<=(2k)Suffix(j) 等价于Rank(i)<(k)Rank(j)||Rank(i)==(k)Rank(j)&&Rank(i)<(i+k)Rank(j+k)
sort(sa,sa+len,cmprank);
for(i=0;i<len;i++)
lrank[i]=rank[i];
//根据SA(2k) 求Rank(2k)
for(rank[sa[0]]=0,i=1;i<len;i++)
{
rank[sa[i]]=rank[sa[i-1]];
if(!equ(sa[i],sa[i-1]))
rank[sa[i]]++;
}
}
}
void gethei(int len)
{
int i=0,d=0,j,s;
memset(h,0,sizeof(h));
//height[i]=LCP(i-1,i)
for(i=0;i<len;i++)
{
if(rank[i]==0)
{
h[rank[i]]=0;
continue;
}
j=rank[i]-1;
d=rank[i];
//Suffix(Rank[i])与Suffix(Rank[i-1]比较相等的字符个数
// i==0或者h[i-1]<=1则从头开始比较两个后缀
//否则的话表示已经有前h[i-1]-1个字符相等 继续比较后面相等字符的个数
if(i==0||h[i-1]<=1)
s=0;
else
s=h[i-1]-1;
for(;sa[d]+s<len&&sa[j]+s<len;s++)
if(str[sa[d]+s]!=str[sa[j]+s]) break;
h[i]=s;
//其实可以根据height[rank[i]]=h[i]求height[]这样可以省去h[]数组空间
}
//heigth[i]=h[sa[i]]
for(i=0;i<len;i++)
height[i]=h[sa[i]];
}
int main()
{
int t;
cin>>t;
getchar();
while(t--)
{
gets(str);
int len=strlen(str);
str[len++]='$';
str[len]=0;
createSA(len);
gethei(len);
int maxid=height[0];
for(int i=1;i<len;i++)
{
int l1=sa[i],l2=sa[i-1];
//因为height[i]表示LCP(i-1,i)
//而题目要求得连续重复的,则只要具有最长公共前缀是连续的
//Suffix(SA[l1])和Suffix(SA[l2])的最长公共前缀是连续 即l1+heigt[i]==l2
if(l1>l2)
swap(l1,l2);
if(l1+height[i]==l2&&height[i]>maxid)
maxid=height[i];
}
cout<<maxid<<endl;
}
return 0;
}
因为zoj数据弱了 其实以上代码不能过评论的那组数据。是我考虑欠缺了..现修改main函数通过枚举结果值来计算。不过感觉太耗时间了 可否有更好的方法？修改main函数代码如下：
bool check(int k,int len)
{
int i,j,a,b;
for(i=0;i<len;i++)
{
if(height[i]>=k) //枚举大于等于k的区间里 只要存在连续段就是结果.
{
a=sa[i-1];
for(j=i;j<len&&height[j]>=k;j++)
{
b=sa[j];
if(a+height[j]==b||b+height[j]==a)
return true;
}
}
}
return false;
}
int main()
{
int t;
cin>>t;
getchar();
while(t--)
{
gets(str);
int len=strlen(str);
str[len++]='$';
str[len]=0;
createSA(len);
gethei(len);
int maxid;
//这样枚举太耗时间了。不知可有更好的方法？
for(maxid=len/2;maxid>=0;maxid--)
{
if(check(maxid,len))
break;
}
cout<<maxid<<endl;
}
return 0;
}
posted on 2009-05-09 11:22
米游 阅读(1677)
评论(5) 编辑 收藏 引用 所属分类:
ACM