UOJ #35. BZOJ 1031 后缀排序 后缀数组模板

真-模板题系列。板子直接用了sort，O(n*logn*logn)的，将就着T吧。

UOJ 35 需要用到高度数组，BZOJ 1031把字符串重复两次求个后缀数组就可以了。

UOJ 35：

#include <bits/stdc++.h> using namespace std; const int maxn=100005; string s; int n,K,Rank[maxn],tmp[maxn],sa[maxn],lcp[maxn]; inline bool compare_sa(int i,int j) { if (Rank[i]!=Rank[j]) return Rank[i]<Rank[j]; else { int ri=(i+K<=n)?Rank[i+K]:-1; int rj=(j+K<=n)?Rank[j+K]:-1; return ri<rj; } } inline void construct_sa(string S,int *sa) { n=S.length(); for (int i=0;i<=n;++i) { sa[i]=i; Rank[i]=i<n?S[i]:-1; } for (K=1;K<=n;K*=2) { sort(sa,sa+n+1,compare_sa); tmp[sa[0]]=0; for (int i=1;i<=n;++i) tmp[sa[i]]=tmp[sa[i-1]]+(compare_sa(sa[i-1],sa[i])?1:0); for (int i=0;i<=n;++i) Rank[i]=tmp[i]; } } inline void construct_lcp(string S,int *sa,int *lcp) { n=S.length(); int h=0; lcp[0]=0; for (int i=0;i<n;++i) { int j=sa[Rank[i]-1]; h=max(h-1,0); for (;j+h<n&&i+h<n;++h) if (S[j+h]!=S[i+h]) break; lcp[Rank[i]-1]=h; } } inline void print() { for (int i=1;i<=n;++i) printf("%d%c",sa[i]+1,i==n?'\n':' '); for (int i=1;i<n;++i) printf("%d%c",lcp[i],i==n?'\n':' '); } int main() { cin>>s; construct_sa(s,sa); construct_lcp(s,sa,lcp); print(); return 0; }

BZOJ 1031：

#include <bits/stdc++.h> using namespace std; const int maxn=200005; string s; int n,K,Rank[maxn],tmp[maxn],sa[maxn],lcp[maxn]; inline bool compare_sa(int i,int j) { if (Rank[i]!=Rank[j]) return Rank[i]<Rank[j]; else { int ri=(i+K<=n)?Rank[i+K]:-1; int rj=(j+K<=n)?Rank[j+K]:-1; return ri<rj; } } inline void construct_sa(string S,int *sa) { n=S.length(); for (int i=0;i<=n;++i) { sa[i]=i; Rank[i]=i<n?S[i]:-1; } for (K=1;K<=n;K*=2) { sort(sa,sa+n+1,compare_sa); tmp[sa[0]]=0; for (int i=1;i<=n;++i) tmp[sa[i]]=tmp[sa[i-1]]+(compare_sa(sa[i-1],sa[i])?1:0); for (int i=0;i<=n;++i) Rank[i]=tmp[i]; } } inline void construct_lcp(string S,int *sa,int *lcp) { n=S.length(); int h=0; lcp[0]=0; for (int i=0;i<n;++i) { int j=sa[Rank[i]-1]; h=max(h-1,0); for (;j+h<n&&i+h<n;++h) if (S[j+h]!=S[i+h]) break; lcp[Rank[i]-1]=h; } } inline void print() { for (int i=1;i<=n;++i) if (sa[i]<(n>>1)) putchar(s[sa[i]+(n>>1)-1]); } int main() { cin>>s; s+=s; construct_sa(s,sa); print(); return 0; }