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

FeedBack:
# re: 病毒的DNA
2009-07-22 11:30 | xxx
这道题哪个OJ有?  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年7月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

留言簿(6)

随笔分类

随笔档案

文章档案

相册

搜索

  •  

最新评论