UOJ35 后缀数组（模板）

2023-07-26 22:49:52

#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

正解：后缀数组

解题报告：
　　模板，第一次交才发现我原来的模板是个萎的，太恐怖了。。。

 //It is made by jump~

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <ctime>

 #include <vector>

 #include <queue>

 #include <map>

 #include <set>

 #ifdef WIN32

 #define OT "%I64d"

 #else

 #define OT "%lld"

 #endif

 using namespace std;

 typedef long long LL;

 const int MAXN = ;

 char ch[MAXN];

 int n,m,tot;

 int wa[MAXN],wb[MAXN],wv[MAXN],c[MAXN];

 int rank[MAXN],height[MAXN];

 int sa[MAXN];

 inline int getint()

 {

        int w=,q=;

        char c=getchar();

        while((c<'' || c>'') && c!='-') c=getchar();

        if (c=='-')  q=, c=getchar();

        while (c>='' && c<='') w=w*+c-'', c=getchar();

        return q ? -w : w;

 }

 inline void da(int m){

     int i,*x=wa,*y=wb;

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

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

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

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

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

     p=;

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

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

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

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

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

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

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

     for(i=;i<=n;i++) x[sa[i]]=(y[sa[i-]]==y[sa[i]] && y[sa[i-]+k]==y[sa[i]+k])?p:++p;

     if(p==n) break; m=p;

     }

 }

 inline void calheight(){

     int i,j,k=;

     for(i=;i<=n;height[rank[i++]]=k)

     for(k?k--: , j=sa[rank[i]-];ch[i+k]==ch[j+k];k++) ;

 }

 inline void work(){

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

     da();

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

     calheight();

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

     printf("\n");

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

 }

 int main()

 {

   work();

   return ;

 }

码农公寓