codevs 1500 后缀排序

时间：2021-02-02 23:36:10

codevs 1500 后缀排序

http://codevs.cn/problem/1500/

 时间限制: 1 s
 空间限制: 128000 KB
 
题目描述 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

4

abab

样例输出 Sample Output

3

1

4

2

数据范围及提示 Data Size & Hint

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

详细解释请参照http://www.cnblogs.com/TheRoadToTheGold/p/6591534.html

#include<cstdio>

#include<algorithm>

#include<cstring>

#define N 15010

using namespace std;

int n,k,p,q=,a[N],v[N],sa[][N],rk[][N],h[N];

char ch[N];

void mul(int *sa,int *rk,int *SA,int *RK)

{

    for(int i=;i<=n;i++) v[rk[sa[i]]]=i;

    for(int i=n;i;i--) if(sa[i]>k) SA[v[rk[sa[i]-k]]--]=sa[i]-k;

    for(int i=n-k+;i<=n;i++) SA[v[rk[i]]--]=i;

    for(int i=;i<=n;i++) RK[SA[i]]=RK[SA[i-]]+(rk[SA[i]]!=rk[SA[i-]]||rk[SA[i-]+k]!=rk[SA[i]+k]);

}

void presa()

{

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

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

    for(int i=;i<=n;i++) sa[p][v[a[i]]--]=i;

    for(int i=;i<=n;i++) rk[p][sa[p][i]]=rk[p][sa[p][i-]]+(a[sa[p][i]]!=a[sa[p][i-]]);

    for(k=;k<n;k<<=,swap(p,q))

    {

        mul(sa[p],rk[p],sa[q],rk[q]);

        if(rk[q][sa[q][n]]==n) //新加的一点儿小优化

        {

            swap(p,q);

            return;

        }

    }

}

int main()

{

    scanf("%d",&n);

    scanf("%s",ch+);

    for(int i=;i<=n;i++) a[i]=ch[i]-'a'+;

    presa();

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

}

2个错误：

① 倍增时k是全局变量，不能再presa（）里重新定义

②新加的优化里，直接reutrn，没有swap，错误

因为正常结束for循环的最后一步一定是swap

相关文章