后缀排序（codevs 1500）

题目描述 Description

天凯是MIT的新生。Prof. HandsomeG给了他一个长度为n的由小写字母构成的字符串，要求他把该字符串的n个后缀(suffix)从小到大排序。

何谓后缀？假设字符串是S=S1S2……Sn，定义Ti=SiSi+1……Sn。T1, T2, …, Tn就叫做S的n个后缀。

关于字符串大小的比较定义如下（比较规则和PASCAL中的定义完全相同，熟悉PASCAL的同学可以跳过此段）：

若A是B的前缀，则A<B；否则令p满足：A1A2…Ap-1=B1B2…Bp-1，Ap<>Bp。如果Ap<Bp，则A<B；否则A>B。

输入描述 Input Description

第一行一个整数n(n<=15000)

第二行是一个长度为n字串。

输出描述 Output Description

输出文件包含n行，第i行是一个整数pi。表示所有的后缀从小到大排序后是Tp1, Tp2, …, Tpn。

样例输入 Sample Input

abab

样例输出 Sample Output

数据范围及提示 Data Size & Hint

说明：后缀排序后的顺序是T3=”ab”, T1=”abab”, T4=”b”, T2=”bab”。所以输出是3, 1, 4, 2。

/*后缀数组裸题*/

#include<cstdio>

#include<iostream>

#define N 15010

using namespace std;

int n,m=,s[N],sa[N],t1[N],t2[N],c[N];

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

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

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

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

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

}

void DA(){

    int *x=t1,*y=t2;

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

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

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

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

    for(int k=,p=;k<=n;k*=,m=p,p=){

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

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

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

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

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

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

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

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

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

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

        if(p>=n) break;

    }

}

int main(){

    char ch[N];

    scanf("%d%s",&n,ch);

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

        s[i]=ch[i];

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

    return ;

}

巴特西

后缀排序（codevs 1500）

最新文章

热门文章