看了羅穗騫和許智磊的神作《后綴數組-處理字符串的有力工具》，《后綴數組》，一個講證明，一個重點講實現，相得益彰。
看了一周了，稍微明白點了，哎！
弄得暈頭轉向，h[]和height[]的關系，sa[]和rank[]的關系，倍增構造sa,繼續學習sa;fighting!!
獻上這兩篇神作供大家交流學習
后綴數組下面一道題，poj1743，最長不重疊重復子串
基本用的羅神的摸板
http://poj.org/problem?id=1743
按羅神思路二分答案
下面代碼
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = 20010;
int wa[maxn],wb[maxn],wv[maxn],ws[maxn];
int sa[maxn];int n;
int cmp(int *r,int a,int b,int l)
{
return r[a]==r[b]&&r[a+l]==r[b+l];
}
void da(int *r,int *sa,int n,int m)
{
int i,j,p,*x=wa,*y=wb,*t;
for(int i=0;i<m;++i)ws[i]=0;
for(int i=0;i<n;++i)++ws[x[i]=r[i]];
for(int i=1;i<m;++i)ws[i]+=ws[i-1];
for(int i=n-1;i>=0;--i)sa[--ws[x[i]]]=i;
for(j=1,p=1;p<n;j*=2,m=p)
{
for(p=0,i=n-j;i<n;++i)y[p++]=i;
for(i=0;i<n;++i)if(sa[i]>=j)y[p++]=sa[i]-j;
for(i=0;i<n;++i)wv[i]=x[y[i]];
for(i=0;i<m;++i)ws[i]=0;
for(i=0;i<n;++i)ws[wv[i]]++;
for(i=1;i<m;++i)ws[i]+=ws[i-1];
for(i=n-1;i>=0;--i)sa[--ws[wv[i]]]=y[i];
for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;++i)
x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}//printf("djsfhuisdhfi\n");
return;
}
int rank[maxn],height[maxn];
void calheight(int *r,int *sa,int n)
{
int i,j,k=0;
for(i=1;i<=n;++i)rank[sa[i]]=i;
for(i=0;i<n;height[rank[i++]]=k)
for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];++k);
return ;
}
int check(int k)
{
int nmin=maxn,nmax=0;
for(int i=1;i<=n;++i)
{
if(height[i]<k)
{
nmin=nmax=sa[i];
}
else
{
nmin=nmin<sa[i]?nmin:sa[i];
nmax=nmax>sa[i]?nmax:sa[i];
if(nmax-nmin>=k)return 1;
}
}
if(nmax-nmin<k)return 0;
return 1;
}
int b_search(int l,int r)
{
int mid;
for(mid=l+((r-l)>>1);l<=r;mid=l+((r-l)>>1))//這里注意移位運算優先級比較低，得加上括號
{
if(check(mid))l=mid+1;else r=mid-1;//printf("djsfhuisdhfi\n");
}
if(check(mid)) return mid;
return 0;
}
int main()
{
while(~scanf("%d",&n)&&n)
{
int num[maxn];
for(int i=0;i<n;++i)scanf("%d",&num[i]);
int r[maxn];r[0]=500;
for(int i=1;i<n;++i)r[i]=num[i]-num[i-1]+100;
r[n]=0;
da(r,sa,n+1,501);
calheight(r,sa,n);
int ans=b_search(0,n>>1)+1;
if(ans>=5)printf("%d\n",ans);
else puts("0");
}
return 0;
}
繼續做后綴數組！！！
posted on 2011-09-07 10:49
ACSeed 閱讀(217)
評論(0) 編輯 收藏 引用