#218-[后缀数组]后缀排序

Description

读入一个由小写字母构成的字符串，求每个后缀的排名以及相邻两个后缀的LCP长度。

Input

一行一个字符串。

Output

第一行用空格隔开的n个数，n为字符串长度，按顺序依次为第1到第n个后缀在所有后缀里面的排名。

第一行用空格隔开的n个数，第i个数表示排名为i的后缀和排名为i-1的后缀的LCP长度，第一个数恒为0。

aabaaaab

Sample Input

4 6 8 1 2 3 5 7 0 3 2 3 1 2 0 1

Sample Output

HINT

n≤50000

Updated By MCHacker

后缀数组模板

#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int MAXN = 50010; int sa[MAXN], rnk[MAXN], height[MAXN], c[MAXN], t[MAXN], t2[MAXN]; char s[MAXN]; void get_sa(int n, int m) { // 找排名 int *x=t, *y=t2; for (int i=0; i<m; ++i) c[i]=0; // 桶清空 for (int i=0; i<n; ++i) ++c[x[i]=s[i]]; // 把字符塞进去 for (int i=1; i<m; ++i) c[i]+=c[i-1]; // 前缀和 for (int i=n-1; i>=0; --i) sa[--c[x[i]]]=i; // 全部放sa里去 for (int k=1; k<=n; k<<=1) { // 倍增 int p=0; for (int i=n-k; i<n; ++i) y[p++]=i; for (int i=0; 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=0; i<n; ++i) ++c[x[y[i]]]; for (int i=1; i<m; ++i) c[i]+=c[i-1]; for (int i=n-1; i>=0; --i) sa[--c[x[y[i]]]]=y[i]; swap(x, y); p=0; x[sa[0]]=p++; for (int i=1; i<n; ++i) { x[sa[i]] = ((y[sa[i-1]]==y[sa[i]])&&(y[sa[i-1]+k]==y[sa[i]+k]))?p-1:p++; } if (p>=n) break; m = p; } } void get_height(int n) { // 找LCP for (int i=0; i<n; ++i) rnk[sa[i]]=i; // 反取排名 int k=0; for (int i=0; i<n; ++i) { if (!rnk[i]) continue; if (k>0) --k; // 据公式取得LCP最小值 int j = sa[rnk[i]-1]; while (s[i+k]==s[j+k]) ++k; // 暴力 height[rnk[i]]=k; } } int main() { scanf("%s", s); int n=strlen(s), m=0; for (int i=0; i<n; ++i) m=max(m, int(s[i])); // 取字符集大小 get_sa(n, m+1); get_height(n); for (int i=0; i<n; ++i) printf("%d ", rnk[i]+1); printf("\n"); for (int i=0; i<n; ++i) printf("%d ", height[i]); return 0; }