bzoj 1692: [Usaco2007 Dec]队列变换
首先像贪心 暴力为比较两个相反的串 贪心标准为以该字母开头，向左or向右的子串字典序大小，先弹小的 把串倒着接到串后边，求一边后缀排顺 然后从两端取rank[],比较小的先弹
#include<cstdio> #include<cstring> #include<algorithm> const int maxn = 600007; int n,m; char c[maxn]; int s[maxn],rank[maxn],sa[maxn],saf[maxn],cnt[maxn]; void rsort() { for(int i=0;i<=m;++i) cnt[i]=0; for(int i=1;i<=n;++i) cnt[rank[saf[i]]]++; for(int i=1;i<=m;++i) cnt[i]+=cnt[i-1]; for(int i=n;i>=1;--i) sa[cnt[rank[saf[i]]]--]=saf[i]; } bool cmp(int *f,int x,int y,int w) { return f[x]==f[y]&&f[x+w]==f[y+w]; } void get_sa() { for(int i=1;i<=n;++i)rank[i]=s[i],saf[i]=i;m=127;rsort(); for(int p=1,w=1,i;p<n;w<<=1,m=p) { for(i=n-w+1,p=0;i<=n;++i)saf[++p]=i; for(i=1;i<=n;++i)if(sa[i]>w)saf[++p]=sa[i]-w; rsort();std::swap(rank,saf);rank[sa[1]]=p=1; for(i=2;i<=n;++i)rank[sa[i]]=cmp(saf,sa[i],sa[i-1],w)?p:++p; } } void init() { scanf("%d",&n);int i=0; while(i<n) {char cc=getchar();if(cc>='A'&&cc<='Z')c[i++]=cc;} getchar();int nn=(n<<1)+1; for(int i=0;i<n;++i)s[i+1]=s[nn-i]=c[i]; n=nn; } void solve() { int l=0,r=(n>>1)-1,cn=0; while(l<=r) { if(rank[l+1]<rank[n-r]) printf("%c",c[l++]),++cn; else printf("%c",c[r--]),cn++; if(cn==80)puts(""),cn=0; } } int main() { init(); get_sa(); solve(); return 0; }转载于:https://www.cnblogs.com/sssy/p/8436486.html
