题意：
给出一个字符串，求将其所有循环串排序之后，，每个串的最后一个字符；
字符串长度<=100000；
题解：
后缀数组裸题。。吧
学长拿这个当例题我还差点不会做。。。
反正就是把字符串倍增之后求后缀数组；
然后按后缀数组来扫一遍求解；
难点就是后缀排序(废话！)；
这里用的是O(nlogn)的倍增+基数排序方法；
模板纯手写。。一堆for循环也是有毒。。
原理上就是利用倍增的思想，将每次的排序转化为二元组的排序问题；
而二元组的排序问题可以利用基数排序O(n)解决而已；
写代码的时候好费劲啊。。。码力果然不够强；
30行模板4数组，Orz PoPoQQQ 60行SA；
代码：
#include<stdio.h>#include<string.h>#include<algorithm>#define N 210000#define S 256using namespace std;char str[N];int rank[N],tr[N],hash[N],sa[N];int main(){int n,m,j,k,cnt;register int i;scanf("%s",str);n=strlen(str);memcpy(str+n,str,sizeof(char)*n);n<<=1;for(i=0;i<n;i++)hash[str[i]]++;for(i=1,cnt=0;i<S;i++)if(hash[i])tr[i]=++cnt;for(i=1;i<S;i++)hash[i]=hash[i-1]+hash[i];for(i=0;i<n;i++)rank[i]=tr[str[i]];for(i=0;i<n;i++)sa[–hash[str[i]]]=i;for(k=2;k<=n;k<<=1){memset(hash,0,sizeof(hash));for(i=0;i<n;i++)hash[rank[i]]++;for(i=1;i<=n;i++)hash[i]=hash[i]+hash[i-1];for(i=n-1;i>=0;i–)if(sa[i]>=(k>>1))tr[sa[i]-(k>>1)]=–hash[rank[sa[i]-(k>>1)]];for(i=1;i<=(k>>1);i++)tr[n-i]=–hash[rank[n-i]];for(i=0;i<n;i++)sa[tr[i]]=i;for(i=1,cnt=0;i<n;i++)if(rank[sa[i-1]]==rank[sa[i]]&&rank[sa[i-1]+(k>>1)]==rank[sa[i]+(k>>1)])tr[sa[i]]=tr[sa[i-1]];elsetr[sa[i]]=++cnt;memcpy(rank,tr,sizeof(tr));if(cnt==n-1)break;}for(i=0;i<n;i++){if(sa[i]<(n>>1))printf("%c",str[sa[i]+(n>>1)-1]);}return 0;}
无做什么，记得为自己而做，那就毫无怨言。
