首页 > ACM题库 > HDU-杭电 > HDU 4552-怪盗基德的挑战书-字符串-[解题报告]HOJ
2015
07-25

HDU 4552-怪盗基德的挑战书-字符串-[解题报告]HOJ

怪盗基德的挑战书

问题描述 :

  “在树最美丽的那天,当时间老人再次把大钟平均分开时,我会降临在灯火之城的金字塔前,带走那最珍贵的笑容。”这是怪盗基德盗取巴黎卢浮宫的《蒙娜丽莎的微笑》这幅画时,挑战书上的内容。
但这次,怪盗基德的挑战书上出现了一串串小写字母“aaab sdfeeddd…”。柯南以小学生的眼睛,超凡高中生的头脑,快速统计各种字母频率,字符串长度,并结合挑战书出现的时间等信息,试图分析怪盗基德的意图。最后,他将线索锁定在字符串的循环次数上。并且进一步推理发现,从字符串的第一位开始,到第i位,形成该字符串的子串(c1, c2, c3 … ci )。对于某一子串ci在该字符串中出现的次数记为ki,则全部子串的循环次数总和AIM = k1 + k2 + … + ki + … + kn,柯南发现,AIM恰好对应一个ASCII码!所以,只要把挑战书上的字符串转变成数字,再找到对应的ASCII码,就可以破解这份挑战书了!
现在,你的任务就是把字符串转变成对应数字,因为ASCII码以及扩展ASCII码全部只有256个,所以,本题只要把结果对256取余即可。

输入:

输入有多组测试数据;
每组测试数据只有一个字符串,由各种小写字母组成,中间无空格。
字符串的长度为L(0 < L <= 100000)。

输出:

输入有多组测试数据;
每组测试数据只有一个字符串,由各种小写字母组成,中间无空格。
字符串的长度为L(0 < L <= 100000)。

样例输入:

aaa
abab

样例输出:

6
6


思路 : 结果为len+lcp(0,i) i从1到n-1
因为
假设 字符串为abab 则abab对应为rank[0]
在abab中 a ab aba abab 分别出现了1次 所以加len
对于后缀数组中的 bab ab b
如果某一个后缀i和abab的最长公共前缀长度为k 那么则会有k个前缀在字符串中出现 如 ab 和abab的最长公共前缀为ab 则a ab分别又出现了一次
所以对于每个后缀i都要加上lcp(0,i) 注意由于rank有效下标从0到n-1 所以i从1到n-1 (在lcp中 i要取得rank[i])

#include <stdio.h>
#include<string.h>
#define maxn 100000+1

#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
int wa[maxn],wb[maxn],wv[maxn],ws[maxn];
int c0(int *r,int a,int b)
{return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];}
int c12(int k,int *r,int a,int b)
{if(k==2) return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);
 else return r[a]<r[b]||r[a]==r[b]&&wv[a+1]<wv[b+1];}
void sort(int *r,int *a,int *b,int n,int m)
{
     int i;
     for(i=0;i<n;i++) wv[i]=r[a[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--) b[--ws[wv[i]]]=a[i];
     return;
}
void dc3(int *r,int *sa,int n,int m)      // r为待匹配数组  n为总长度 m为字符范围
{
     int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;
     r[n]=r[n+1]=0;
     for(i=0;i<n;i++) if(i%3!=0) wa[tbc++]=i;
     sort(r+2,wa,wb,tbc,m);
     sort(r+1,wb,wa,tbc,m);
     sort(r,wa,wb,tbc,m);
     for(p=1,rn[F(wb[0])]=0,i=1;i<tbc;i++)
     rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;
     if(p<tbc) dc3(rn,san,tbc,p);
     else for(i=0;i<tbc;i++) san[rn[i]]=i;
     for(i=0;i<tbc;i++) if(san[i]<tb) wb[ta++]=san[i]*3;
     if(n%3==1) wb[ta++]=n-1;
     sort(r,wb,wa,ta,m);
     for(i=0;i<tbc;i++) wv[wb[i]=G(san[i])]=i;
     for(i=0,j=0,p=0;i<ta && j<tbc;p++)
     sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
     for(;i<ta;p++) sa[p]=wa[i++];
     for(;j<tbc;p++) sa[p]=wb[j++];
     return;
}
int rank[maxn],height[maxn];
void calheight(int *r,int *sa,int n) //  求height数组。
{
     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 RMQ[maxn];
int mm[maxn];
int best[20][maxn];//best[i][j] 表示从j开始的长度为2的i次方的一段元素的最小值
void initRMQ(int n)
{
     int i,j,a,b;
     for(mm[0]=-1,i=1;i<=n;i++)
     mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
     for(i=1;i<=n;i++) best[0][i]=i;
     for(i=1;i<=mm[n];i++)
     for(j=1;j<=n+1-(1<<i);j++)
     {
       a=best[i-1][j];
       b=best[i-1][j+(1<<(i-1))];
       if(RMQ[a]<RMQ[b]) best[i][j]=a;
       else best[i][j]=b;
     }
     return;
}
int askRMQ(int a,int b)//询问a,b后缀的最长公共前缀
{
    int t;
    t=mm[b-a+1];b-=(1<<t)-1;
    a=best[t][a];b=best[t][b];
    return RMQ[a]<RMQ[b]?a:b;
}
int lcp(int a,int b)
{
    int t;
    a=rank[a];b=rank[b];
    if(a>b) {t=a;a=b;b=t;}
    return(height[askRMQ(a+1,b)]);
}

char c;
int r[maxn*3],sa[maxn*3];
int ans[maxn];
char str[maxn*3];
int main()
{
    int i,j,n,cas;
      while(scanf("%s",str)!=EOF)
      {
      n=strlen(str);
      for(i=0;i<n;i++)  r[i]=str[i]-'a'+1;
      r[n]=0;
      dc3(r,sa,n+1,30);//千万注意是n+1
      calheight(r,sa,n);
      for(i=1;i<=n;i++)  RMQ[i]=height[i];
      initRMQ(n);

     /*   for(i=0; i<n+1; i++)  // rank[i] : suffix(i)排第几
           printf("rank[%d] =  %d\n",i,rank[i]);
        printf("\n");
        for(i=0; i<n+1; i++)   // sa[i] : 排在第i个的是谁
           printf("sa[%d] =  %d\n",i,sa[i]);
        for(i=0;i<n+1;i++)
            printf("height[%d]=%d\n",i,height[i]);
     */

///     对后缀数组没有直观认识 可以打印出来上面注释的内容
/*
        由于我们是从0开始输入的,所以注意rank的有效下标是从0到n-1的
        sa的下标是从1到n的   height也是从1到n的
*/
        int ans=n%256;
        for(i=1;i<n;i++)
        {
             ans+=lcp(0,i);
        //printf("%d %d\n",i,ans);
             ans%=256;
        }
        printf("%d\n",ans%256);
    }
    return 0;
}

 

参考:http://blog.csdn.net/hnust_xiehonghao/article/details/9264169