BZOJ1031 [JSOI2007]字符加密Cipher

2014.12.08 20:48 Mon| 5 visits oi_2015| 2015_刷题日常| Text

很简单一道后缀数组入门题,测试模板专用。

这么裸的题现在很少见了呢~

Solution

首先将原串直接复制一遍,求后缀数组,之后按顺序输出相应字符即可。

Code

#include <bits/stdc++.h>
using namespace std;
#define N 200005

char str[N];
int n,c[N],x[N],y[N],sa[N],rank[N],height[N];

inline bool same(int a,int b,int k)
{
    return y[a]==y[b] && ((a+k>=n&&b+k>=n)||(a+k<n&&b+k<n&&y[a+k]==y[b+k]));
}

void get_sa(int m=256)
{
    for(int i=0;i<n;i++) c[x[i]=str[i]]++;
    for(int i=1;i<m;i++) c[i]+=c[i-1];
    for(int i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
    for(int k=1;k<n;k<<=1)
    {
        int p=0;
        for(int i=n-k;i<n;i++) y[p++]=i;
        for(int i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;
        memset(c,0,m*sizeof(int));
        for(int i=0;i<n;i++) c[x[y[i]]]++;
        for(int i=1;i<m;i++) c[i]+=c[i-1];
        for(int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
        for(int i=0;i<n;i++) y[i]=x[i];
        m=0; x[sa[0]]=0;
        for(int i=1;i<n;i++)
            x[sa[i]]=same(sa[i-1],sa[i],k)?m:++m;
        if(++m==n) break;
    }
}

void get_height()
{
    for(int i=0;i<n;i++) rank[sa[i]]=i;
    for(int i=0,j,k=0;i<n;height[rank[i++]]=k)
        if(rank[i]) for(k?k--:0,j=sa[rank[i]-1];str[i+k]==str[j+k];k++);
}

int main()
{
    scanf("%s",str);
    n=strlen(str);
    memcpy(str+n,str,n*sizeof(char));
    n<<=1;
    get_sa(256);
    for(int i=0;i<n;i++)
        if(sa[i]<n/2)
            putchar(str[sa[i]+n/2-1]);
    puts("");
    return 0;
}