题意：
给出一个字符串；
求这个字符串的后缀数组和height数组；
长度<=100000；
题解：
后缀数组纯裸题；
不得不说众人的力量是伟大的，，VFK的毒瘤功底是有目共睹的；
A掉这道题，模板又是有了一些改动= =；
总之uoj的数据真挺强的，推荐去交一下；
而且可以看WA的测试点。。然后我case1case2case3连挂三次。。
代码：
#include<stdio.h>#include<string.h>#include<algorithm>#define N 110000#define S 256using namespace std;char str[N];int n;int hash[N],rank[N],tr[N],sa[N],h[N];bool cmp(int x,int y,int len){if(x+len>=n)return 0;return rank[x]==rank[y]&&rank[x+len]==rank[y+len];}void getSA(char *str){register int i;int k,cnt;for(i=0;i<n;i++)hash[str[i]]++;for(i=0,cnt=-1;i<S;i++)if(hash[i])tr[i]=++cnt;for(i=1;i<S;i++)hash[i]=hash[i]+hash[i-1];for(i=0;i<n;i++)rank[i]=tr[str[i]],sa[–hash[str[i]]]=i;for(k=2;cnt!=n-1;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++)tr[sa[i]]=cmp(sa[i-1],sa[i],k>>1)?cnt:++cnt;memcpy(rank,tr,sizeof(tr));}for(i=0;i<=n;i++){if(rank[i])for(k=max(h[rank[i-1]]-1,1);k<n;k++){if(str[sa[rank[i]]+k-1]==str[sa[rank[i]-1]+k-1])h[rank[i]]=k;elsebreak;}}}int main(){int i,j,k,cnt,l,r,mid;scanf("%s",str);n=strlen(str);getSA(str);for(i=0;i<n;i++)printf("%d ",sa[i]+1);putchar('\n');for(i=1;i<n;i++)printf("%d ",h[i]);return 0;}
每个人在他的人生发轫之初，总有一段时光，
