uoj35 后缀排序

题目链接：http://uoj.ac/problem/35

这是一道模板题。

读入一个长度为 n 的由小写英文字母组成的字符串，请把这个字符串的所有非空后缀按字典序从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 1 到 n。

除此之外为了进一步证明你确实有给后缀排序的超能力，请另外输出 n−1 个整数分别表示排序后相邻后缀的最长公共前缀的长度。

输入格式

一行一个长度为 n 的仅包含小写英文字母的字符串。

输出格式

第一行 n 个整数，第 i 个整数表示排名为 i 的后缀的第一个字符在原串中的位置。

第二行 n−1个整数，第 i 个整数表示排名为 i 和排名为 i+1 的后缀的最长公共前缀的长度。

样例一

input

ababa

output

5 3 1 4 2
1 3 0 2

explanation

排序后结果为：

1. a
2. aba
3. ababa
4. ba
5. baba

限制与约定

1≤n≤10^5

时间限制：1s

空间限制：256MB

感想：

对uoj非常的资瓷啊，后缀数组裸题，不懂的自行百度

献上一个大爷的博客链接：http://blog.csdn.net/shiqi_614/article/details/7982915

代码

#include <cstdio>

#include <cstring>

using namespace std;

int i,j,k,n,m,x,y,t,a[],b[],b1[],d[],rk[],p[],h[],s1[];

int height[],ans1[];

char s[];

struct data{int x,y;}c[],e[];

void get_sa(){

    for (i=;i<=n;i++)b[s[i]-'a']=;

    for (i=;i<;i++)b[i]+=b[i-];

    for (i=;i<=n;i++)a[i]=b[s[i]-'a'];

    for (k=;k<=n;k*=){

        for (i=;i<=n;i++)c[i].x=a[i],c[i].y=a[i+k];

        memset(b,,sizeof b);

        for (i=;i<=n;i++)b[c[i].y]++;

        for (i=;i<=n;i++)b[i]+=b[i-];

        for (i=;i<=n;i++)d[b[c[i].y]]=i,b[c[i].y]--;

        for (i=;i<=n;i++)e[i]=c[d[i]];

        for (i=;i<=n;i++)c[i]=e[i];

        for (i=;i<=n;i++)p[i]=d[i];

        memset(b,,sizeof b);

        for (i=;i<=n;i++)b[c[i].x]++;

        for (i=;i<=n;i++)b[i]+=b[i-];

        for (i=n;i>=;i--)d[b[c[i].x]]=i,b[c[i].x]--;

        for (i=;i<=n;i++)e[i]=c[d[i]],rk[i]=d[i];

        for (i=;i<=n;i++)c[i]=e[i];

        s1[]=;

        for (i=;i<=n;i++)if (c[i].x!=c[i-].x||c[i].y!=c[i-].y)s1[i]=s1[i-]+;else s1[i]=s1[i-];

        for (i=;i<=n;i++)a[p[rk[i]]]=s1[i];

    }

    for (i=;i<=n;i++)rk[a[i]]=i;

    for (i=;i<=n;i++)printf("%d ",rk[i]);printf("\n");

}

void get_h(){

    int k=;

    for (int i=;i<=n;i++){

        if (a[i]==) h[i]=k=;

        else{

            j=rk[a[i]-];

            if (k>) k--;

            while (i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) k++;

            h[i]=k;

        }

        height[a[i]]=h[i];

    }

    for (int i=; i<=n; i++) printf("%d ",height[i]);

}

int main(){

    gets(s);

    n=strlen(s);

    for (i=n;i>=;i--)s[i]=s[i-];

    get_sa();

    get_h();

    return ;

}