/*初看這題 以為是傳統意義上的最長重復子串.其實不然,看例子就明白*/
接觸這題后才開始看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
米游 閱讀(1692)
評論(5) 編輯 收藏 引用 所屬分類:
ACM