首页 > > 程序设计 > C/C++ >

(HDU 5558) 2015ACM/ICPC亚洲区合肥站---Alice…

2018-06-17 23:40:14来源：未知阅读 ()

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=5558

Problem Description

Alice wants to send a classified message to Bob. She tries to encrypt the message with her original encryption method. The message is a string

Input

The first line of input contains an integer

Output

For each test case, output a single line consisting of “Case #X:” first.

Sample Input

aaaaaa

aaaaabbbbbaaabbc

Sample Output

Case #1:

-1 97

5 0

Case #2:

-1 97

4 0

-1 98

4 5

5 2

-1 99

Source

2015ACM/ICPC亚洲区合肥站-重现赛（感谢中科大）

Recommend

wange2014 | We have carefully selected several similar problems for you: 5932 5931 5930 5929 5928

题意：输入一个只含有小写英文字母的字符串s[]，现在进行计算，对于当前位置i 在0~i-1 中找到j 使得后缀suffix[i] 和 suffix[j] 的公共前缀最长（设公共前缀长为k），输出长度和j，如果有多个j公共前缀长度一样，输出最小的j ，然后i=i+k 重复上述过程，直至i>=len;

思路：先用后缀数组模板计算出名次数组和后缀数组及最长公共前缀height[]数组，然后对于i 求出i的排名，然后根据i的排名，向比i大和小的排名找，取一个最大值；

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <bitset>
using namespace std;
const int N=1e5+5;
char s[N];
int wa[N],wb[N],wv[N],wss[N];
int rankk[N],height[N],sa[N];
int cmp(int *r,int a,int b,int l){
   return r[a]==r[b]&&r[a+l]==r[b+l];
}
void da(char *r,int *sa,int n,int m)
{
    int i,j,p,*x=wa,*y=wb,*t;
    for(i=0;i<m;i++) wss[i]=0;
    for(i=0;i<n;i++) wss[x[i]=r[i]]++;
    for(i=1;i<m;i++) wss[i]+=wss[i-1];
    for(i=n-1;i>=0;i--) sa[--wss[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++) wss[i]=0;
        for(i=0;i<n;i++) wss[wv[i]]++;
        for(i=1;i<m;i++) wss[i]+=wss[i-1];
        for(i=n-1;i>=0;i--) sa[--wss[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++;
    }
    return ;
}
void calheight(char *r,int *sa,int n)
{
    int i,j,k=0;
    for(i=1;i<=n;i++) rankk[sa[i]]=i;
    for(i=0;i<n;height[rankk[i++]]=k)
        for(k?k--:0,j=sa[rankk[i]-1];r[i+k]==r[j+k];k++);
    return ;
}

int main()
{
    int T,Case=1;
    cin>>T;
    while(T--)
    {
        scanf("%s",s);
        int len=strlen(s);
        da(s,sa,len+1,130);
        calheight(s,sa,len);
        printf("Case #%d:\n",Case++);
        int i=0;
        while(i<len)
       {
           int pos,k=0;
           int rk=rankk[i];
           int d=height[rk];
           for(int j=rk;j>=1&&height[j]!=0;j--)
           {
               d=min(d,height[j]);
               if(d<k) break;
               if(sa[j-1]<i&&((d>k)||(d==k&&sa[j-1]<pos))) {
                    k=d; pos=sa[j-1];
               }
           }
           if(rk<len){
                d=height[rk+1];
                for(int j=rk+1; j<=len&&height[j]!=0; j++)
                {
                     d=min(d,height[j]);
                     if(d<k)  break;
                     if(sa[j]<i&&((d>k)||(d==k&&sa[j]<pos))) {
                        k=d; pos=sa[j];
                     }
                }
           }
           if(k) printf("%d %d\n",k,pos),i+=k;
           else  printf("%d %d\n",-1,(int)s[i++]);
       }
    }
    return 0;
}

方法二：集合查找

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <bitset>
using namespace std;
const int N=1e5+5;
char s[N];
int wa[N],wb[N],wv[N],wss[N];
int cmp(int *r,int a,int b,int l){
   return r[a]==r[b]&&r[a+l]==r[b+l];
}
void da(char *r,int *sa,int n,int m)
{
    int i,j,p,*x=wa,*y=wb,*t;
    for(i=0;i<m;i++) wss[i]=0;
    for(i=0;i<n;i++) wss[x[i]=r[i]]++;
    for(i=1;i<m;i++) wss[i]+=wss[i-1];
    for(i=n-1;i>=0;i--) sa[--wss[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++) wss[i]=0;
        for(i=0;i<n;i++) wss[wv[i]]++;
        for(i=1;i<m;i++) wss[i]+=wss[i-1];
        for(i=n-1;i>=0;i--) sa[--wss[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++;
    }
    return ;
}
int rankk[N],height[N],sa[N],m[20][N];
void calheight(char *r,int *sa,int n)
{
    int i,j,k=0;
    for(int i=1;i<=n;i++) rankk[sa[i]]=i;
    for(i=0;i<n;height[rankk[i++]]=k)
        for(k?k--:0,j=sa[rankk[i]-1];r[i+k]==r[j+k];k++);
    return ;
}
set<int>se;
set<int>:: iterator it1,it2;

int main()
{
    int T,Case=1;
    cin>>T;
    while(T--)
    {
        scanf("%s",s);
        int len=strlen(s);
        da(s,sa,len+1,130);
        calheight(s,sa,len);
        memset(m,0,sizeof(m));
        for(int i=2;i<=len;i++)
            m[1][i-1]=height[i];
        for(int i=2;i<=(int)(log(len)/log(2));i++)
        {
            for(int j=1;j+(1<<i)-1<=len;j++)
            m[i][j]=min(height[j+(1<<(i-1))],min(m[i-1][j],m[i-1][j+(1<<(i-1))]));
        }
        printf("Case #%d:\n",Case++);
        int tot=0,minn=-999,maxn=9999999;
        se.clear();
        se.insert(minn);
        se.insert(maxn);
        while(tot<len)
        {
            int k=0,p;
            int pos=tot;
            it1=se.upper_bound(rankk[tot]);
            it2=it1;
            while(*it1!=maxn)
            {
                int v=(int)(log(*it1-rankk[tot]+1)/log(2));
                int f=min(m[v][rankk[tot]],m[v][*it1-(1<<v)+1]);
                if(f<k||f==0) break;
                if(f>k||(f==k&&sa[*it1]<p)){
                    k=f;
                    p=sa[*it1];
                }
                it1++;
            }
            it2--;
            while(*it2!=minn){
                int v=(int)(log(rankk[tot]-*it2+1)/log(2));
                int f=min(m[v][*it2],m[v][rankk[tot]-(1<<v)+1]);
                if(f<k||f==0) break;
                if(f>k||(f==k&&sa[*it2]<p)){
                    k=f;
                    p=sa[*it2];
                }
                it2--;
            }
            if(k==0) {
                printf("%d %d\n",-1,(int)s[tot]);
                tot++;
            }
            else {
                printf("%d %d\n",k,p);
                tot+=k;
            }
            for(;pos<tot;pos++)
                se.insert(rankk[pos]);
        }
    }
    return 0;
}