花了半天的時間終于 AC 了
貼一下代碼：
#include<iostream>
#define?Rank(x)?rank[(x)<?(n+1)]
using?namespace?std;
char?a[100000],c[5000],b[5000],d[100000];
int?sa[5001],height[5001],rank[5001],n,sum[5001],h[5001],_sa[5001],_rank[5001],m,ans[20][5001],tr[5001],tl[5001],maxk,maxi,lft[100001],rght[100001],leftt[100001],rightt[100001];
struct?node
{
????int?th;
????char?s;
}r[10000];
int?cmps(const?void?*a,const?void?*b)
{
????return?(*(node?*)a).s-(*(node?*)b).s;
}
int?cmpth(const?void?*a,const?void?*b)
{
????return?(*(node?*)a).th-(*(node?*)b).th;
}
void?getsa()
{
????qsort(r+1,n,sizeof(node),cmps);
????int?p=0;
????for(int?i=1;i<=n;++i)
????????if(r[i].s!=r[i-1].s)
????????{
????????????rank[r[i].th]=++p;
????????????sa[i]=r[i].th;
????????}
????????else
????????{
????????????rank[r[i].th]=p;
????????????sa[i]=r[i].th;
????????}
?????qsort(r+1,n,sizeof(node),cmpth);
?????for(int?l=1;p<n;l<<=1)
?????{
?????????memset(sum,0,sizeof(sum));
?????????memset(h,0,sizeof(h));
?????????for(int?i=1;i<=n;++i)
?????????????++sum[rank[i]+1];
????????for(int?i=1;i<=p;++i)
????????????sum[i]+=sum[i-1];????
?????????for(int?i=n-l+1;i<=n;++i)
????????????_sa[sum[rank[i]]+(++h[rank[i]])]=i;
????????for(int?i=1;i<=n;++i)
?????????????if(sa[i]>l)
?????????????????_sa[sum[rank[sa[i]-l]]+(++h[rank[sa[i]-l]])]=sa[i]-l;
????????memcpy(sa,_sa,sizeof(_sa));
????????p=0;
????????for(int?i=1;i<=n;++i)
????????????_rank[sa[i]]=((rank[sa[i]]==rank[sa[i-1]])&&(Rank(sa[i]+l)==Rank(sa[i-1]+l)))?p:++p;
????????memcpy(rank,_rank,sizeof(_rank));????????????
?????}
}
void?getans()
{
????for(int?i=1;i<=n;++i)
????????ans[0][i]=height[i];
????for(int?i=1;1<<i<=n;++i)
????????for(int?j=1;j+i-1<=n;++j)
????????????ans[i][j]=ans[i-1][j]<?ans[i-1][j+(1<<(i-1))];
}
int?askRMQ(int?s,int?t)
{
????for(int?i=0;;++i)
????????if(t-s<1<<i)
????????????return?ans[i-1][s]<?ans[i-1][t-(1<<(i-1))+1];
}
void?getheight(bool?flag)?
{
????for(int?k=0,i=1,j;i<=n;height[rank[i++]-1]=k)
????????for(k?--k:0,j=sa[rank[i]-1];r[i+k].s==r[j+k].s;++k);
?????getans();
?????if(flag)
?????{
?????????tr[1]=m;
?????????for(int?i=2;i<=m;++i)
?????????????tr[i]=askRMQ(rank[1]<?rank[i-1],rank[1]>?rank[i-1]);
?????}
?????else
?????{
?????????tl[1]=m;
?????????for(int?i=2;i<=m;++i)
?????????????tl[i]=askRMQ(rank[1]<?rank[i-1],rank[1]>?rank[i-1]);????????????
?????}
}
int?main()
{
????scanf("%s",a);
????scanf("%s",b);
????m=strlen(a);
????n=strlen(b);
????for(int?i=0;i<n;++i)
????{
????????r[i+1].s=b[i];
????????r[i+1].th=i+1;
????}
????getsa();
????getheight(1);
????maxk=-1;
????for(int?i=0;i<m;++i)
????{
????????if(maxk<i)
????????{
????????????for(int?j=0;;++j)
????????????????if(j==n||i+j==m||a[i+j]!=b[j])
????????????????{
????????????????????maxk=i+j-1;
????????????????????maxi=i;
????????????????????rght[i]=j;
????????????????????break;
????????????????}
????????}
????????else
????????{
????????????if(tr[maxi-i+1]>=maxk-i+1)
????????????????for(int?j=maxk-i+1;;++j)
????????????????????if(j==n||i+j==m||a[i+j]!=b[j])
????????????????????{
????????????????????????maxk=i+j-1;
????????????????????????maxi=i;
????????????????????????rght[i]=j;????????????????????????
????????????????????}
????????????else
????????????????rght[i]=tr[maxi-i+1];
????????}
????}
????maxk=-1;
????for(int?i=0;i<n;++i)
????{
????????c[i]=r[i+1].s=b[n-i-1];
????????r[i+1].th=i+1;
????}
????getsa();
????getheight(0);
????for(int?i=0;i<m;++i)
????????d[i]=a[m-i-1];
????for(int?i=0;i<m;++i)
????{
????????if(maxk<i)
????????{
????????????for(int?j=0;;++j)
????????????????if(j==n||i+j==m||d[i+j]!=c[j])
????????????????{
????????????????????maxk=i+j-1;
????????????????????maxi=i;
????????????????????lft[i]=j;
????????????????????break;
????????????????}
????????}
????????else
????????{
????????????if(tl[maxi-i+1]>=maxk-i+1)
????????????????for(int?j=maxk-i+1;;++j)
????????????????????if(j==n||i+j==m||d[i+j]!=c[j])
????????????????????{
????????????????????????maxk=i+j;
????????????????????????maxi=i;
????????????????????????lft[i]=j;????????????????????????
????????????????????}
????????????else
????????????????lft[i]=tl[maxi-i+1];
????????}
????}
????for(int?i=m-1;i>=0;--i)
????????if(lft[i]==n&&i+n!=m)
????????????leftt[i]=lft[i]+leftt[i+n];
????????else
????????????leftt[i]=lft[i];
????for(int?i=m-1;i>=0;--i)
????????if(rght[i]==n&&i+n!=m)
????????????rightt[i]=rght[i]+rightt[i+n];
????????else
????????????rightt[i]=rght[i];
????int?maxl=0;
????for(int?i=0;i<m;++i)
????????maxl>?=rightt[i]+leftt[m-i];
????
????if(maxl<n)
????????puts("0");
????else
????????printf("%f\n",double(maxl)/m);
????return?0;
}
這道題是03年饒向榮論文里的一道題 有一定難度
除了T數組的求解和論文中不同外 沒有什么不同
論文中說的方法沒看懂 期望有牛人能講一下
我的方法很簡單就是通過后綴數組完成的 但大大增加了代碼長度這好象是我寫oi題目寫的最長的一道了(我太弱了) 一個不錯的開始期望以后每天都能AC并且要多
posted on 2009-04-13 23:33
250 閱讀(1555)
評論(1) 編輯 收藏 引用 所屬分類:
oi