花了半天的时间终于 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 阅读(1539)
评论(1) 编辑 收藏 引用 所属分类:
oi