35. 后缀排序

统计

描述

提交

自定义测试

这是一道模板题。

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

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

输入格式

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

输出格式

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

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

样例一

input

ababa

output

5 3 1 4 2

1 3 0 2

explanation

排序后结果为：

a

aba

ababa

ba

baba

限制与约定

1≤n≤1051≤n≤105

时间限制：1s1s

空间限制：256MB256MB

/*

求height裸题.

数组从0开始有一个点过不去

然后改了从1开始，改了好久。。

*/

#include<iostream>

#include<cstring>

#include<cstdio>

#define MAXN 100001

using namespace std;

int n,m=130,s[MAXN],sa[MAXN],ht[MAXN],rank[MAXN],t1[MAXN],t2[MAXN],c[MAXN];

char ch[MAXN];

bool cmp(int *y,int a,int b,int k)

{

    int a1=y[a],b1=y[b];

    int a2=a+k>n?-1:y[a+k];

    int b2=b+k>n?-1:y[b+k];

    return a1==b1&&a2==b2;

}

void slovesa()

{

    int *x=t1,*y=t2;

    for(int i=1;i<=n;i++) c[x[i]=s[i]]++;

    for(int i=2;i<m;i++) c[i]+=c[i-1];

    for(int i=n;i>=1;i--) sa[c[x[i]]--]=i;

    for(int k=1,p=0;k<=n;k<<=1,m=p+1,p=0)

    {

        for(int i=n-k+1;i<=n;i++) y[++p]=i;

        for(int i=1;i<=n;i++) if(sa[i]>k) y[++p]=sa[i]-k;

        for(int i=0;i<m;i++) c[i]=0;

        for(int i=1;i<=n;i++) c[x[y[i]]]++;

        for(int i=2;i<m;i++) c[i]+=c[i-1];

        for(int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i];

        swap(x,y);x[sa[1]]=1,p=1;

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

        {

            if(cmp(y,sa[i-1],sa[i],k)) x[sa[i]]=p;

            else x[sa[i]]=++p;

        }

        if(p>n) break;

    }

}

void sloveheight()

{

    int k=0;

    for(int i=1;i<=n;i++) rank[sa[i]]=i;

    for(int i=1;i<=n;ht[rank[i++]]=k)

    {

        int j=sa[rank[i]-1];

        if(k) k--;

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

    }

    ht[1]=0;

}

int main()

{

    scanf("%s",ch+1);n=strlen(ch+1);

    for(int i=1;i<=n;i++) s[i]=ch[i];

    slovesa(),sloveheight();

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

    printf("\n");

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

    return 0;

}