[后缀数组]poj 3581：Sequence

大致题意：

    给出n个数，把这个数列分为三段，再把三段反转后连接在一起成为一个新串，求字典序最小的新串。

 

大致思路：

    由于需要翻转，所以在输入时就按照反序输入。比如样例输入是5     10 1 2 3 4。我们从后向前读入就变为5     4 3 2 1 10。对这列数求出后缀数组。在大于2的后最中找到最小的后缀并输出。对于剩下的前缀s，我们把s串接到自己后面，也就是ss。再对这个串求出后缀数组，然后再把s中最小的前缀输出。最后把剩下的串输出。

 

对于第二步为什么要复制剩余串接在后面，用下面案例说明

6

10 1 2 2 3 4

 

第一步翻转后得到

4 3 2 2 1 10

 

求出后缀数组后得到最小的后缀便是：1 10，将其输出

剩下来的串是 4 3 2 2.

 

我们如果直接从剩余串中找到最小后缀的话会产生以下结果。

最小后缀是 2，输出。

输出剩余串 4 3 2。

最后得到1 10 2 4 3 2  很明显是wrong的

 

 

我们把剩余的串复制到剩余串的后面。

对 4 3 2 2 4 3 2 2求出后缀数组。

得到前四个字符的最小的后缀是 2 2，输出。

输出剩余串 4 3.

得到1 10 2 2 4 3 

 

 

注意这里面数串中数字的范围没有给出，所以原来倍增算法模版中的桶排序需要改成快排。

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int Max = 500005;
const int inf=1<<30;
int n, num[Max];
int sa[Max], rankk[Max], height[Max];
int wa[Max], wb[Max], wv[Max], wd[Max];


int sa1[Max],rankk1[Max],c[Max],h[Max];

int poww,count;

int cmp(const void *a,const void *b){
    int x=*(int*)a;
    int y=*(int*)b;
    if(rankk[x]!=rankk[y])
        return(1);
    else
        if(rankk[x+poww]!=rankk[y+poww])
            return(1);
        else
            return(0);
}

int cmp1(const void *a,const void *b){
    return num[*((int *)a)]-num[*((int *)b)];
}

void da(int *m,int n){
    int i,j,k;
    for(i=0;i<n;i++)sa[i]=i;
    qsort(sa,n,sizeof(int),cmp1);
    for(i=0,j=0;i<n;i++){
        if(i>0&&m[sa[i]]!=m[sa[i-1]])
            j++;
            rankk[sa[i]]=j;
    }

    for(poww=1;poww<n;poww*=2){
        for(i=0;i<n;i++)c[i]=0;
        for(i=0;i<n;i++)
            if(sa[i]+poww<n)c[rankk[sa[i]+poww]]++;
            else c[rankk[sa[i]]]++;
        for(i=1;i<n;i++)c[i]+=c[i-1];
        for(i=n-1;i>=0;i--)
            if(sa[i]+poww<n)sa1[--c[rankk[sa[i]+poww]]]=sa[i];
            else sa1[--c[rankk[sa[i]]]]=sa[i];
        for(i=0;i<n;i++)c[i]=0;
        for(i=0;i<n;i++)c[rankk[sa1[i]]]++;
        for(i=1;i<n;i++)c[i]+=c[i-1];
        for(i=n-1;i>=0;i--)sa[--c[rankk[sa1[i]]]]=sa1[i];
        for(i=0,j=0;i<n;i++){
            if(i>0&&cmp(&sa[i],&sa[i-1])!=0)j++;
            rankk1[sa[i]]=j;
        }
        for(i=0;i<n;i++) rankk[i]=rankk1[i];
    }
}

int main(){
    int n,i,j,ans,start,len,mmax,mmin,lab1,lab2;
   // while(!=EOF){
    scanf("%d",&n);
    mmax=-inf;
    for(i=n-1;i>=0;i--){
        scanf("%d",&num[i]);
        num[i]++;
        mmax=max(mmax,num[i]);
    }
    num[n]=0;
    da(num,n+1);
 //   calHeight(num,n);
    mmin=inf;
    for(i=2;i<n;i++){
        if(rankk[i]<mmin){
            mmin=rankk[i];
            lab1=i;
        }
    }
    for(i=lab1;i<n;i++){
        printf("%d\n",num[i]-1);
    }

    int k=lab1;
    for(i=0;i<lab1;i++){
        num[k++]=num[i];
    }
    mmin=inf;
    num[k]=0;
    da(num,k+1);
   // calHeight(num,k);
    for(i=1;i<lab1;i++){
        if(rankk[i]<mmin){
            mmin=rankk[i];
            lab2=i;
        }
    }
    for(i=lab2;i<lab1;i++){
        printf("%d\n",num[i]-1);
    }
    for(i=0;i<lab2;i++){
        printf("%d\n",num[i]-1);
    }
   // }
    return 0;
}

评论

2 楼 暴风雪 2012-02-24  

luozhong915127 写道

输入是5     10 1 2 3 4。我们从后向前读入就变为5     4 3 2 1 10会是这样的结果吗，

你如果看题目的话就会知道，第一个数字(这里的5)表示的是这个数列中数字的个数，自然不用反过来~~囧

1 楼 luozhong915127 2012-02-24  

输入是5     10 1 2 3 4。我们从后向前读入就变为5     4 3 2 1 10会是这样的结果吗，