真·模板题（然而还是TLE了，tyvj真是个毒瘤，输出double什么的就是 -0.00000000，这些就TLE2333）

简单的说一下本蒟蒻看了一天后缀数组的收获（这东西太神了，，，wcwc，，收获到我的膝盖233，还是不太理解这个神奇的东西）（鉴于本人太虚，只看了一下倍增，照着黄学长扒了一个板子23333）

一共有3个神奇的数组，sa(Sufiix Array)，rank，height

对于前两个数组的求法，用基数排序的方法，每次搞出长度为2^i（除了最后，，）的子串的rank，然后用这些子串（当前长度为2^i和下一个），来更新出长度为2^(i+1)的子串

所以，一共是进行了log(strlen(ch))次的。

里面有一些小细节自己YY一下就好了，（吐槽，各种各样的sa[v[rank[..]..].]太恶心了2333）

1 #include
     
       2 #define N 100005<<2 3 #define LL long long 4 #define inf 0x3f3f3f3f 5 using namespace std; 6 inline int ra() 7 { 8     int x=0,f=1; char ch=getchar(); 9     while (ch<'0' || ch>'9') {
   if (ch=='-') f=-1; ch=getchar();}10     while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}11     return x*f;12 }13 char ch[N];14 int n,k,p,q;15 int a[N],rank[2][N],sa[2][N],height[N],v[N];16 void cal_sa(int sa[N], int rank[N], int Sa[N], int Rank[N])17 {18     for (int i=1; i<=n; i++) v[rank[sa[i]]]=i;19     for (int i=n; i>=1; i--)20         if (sa[i]>k) Sa[v[rank[sa[i]-k]]--]=sa[i]-k;21     for (int i=n-k+1; i<=n; i++) Sa[v[rank[i]]--]=i;22     for (int i=1; i<=n; i++) Rank[Sa[i]]=Rank[Sa[i-1]]+(rank[Sa[i]]!=rank[Sa[i-1]] || rank[Sa[i]+k]!=rank[Sa[i-1]+k]);23 }24 void get_height()25 {26     k=0;27     for (int i=1; i<=n; i++)28     {29         if (rank[p][i]==1) height[1]=0;30         else{31             int j=sa[p][rank[p][i]-1];32             while (a[i+k]==a[j+k]) k++;33             height[rank[p][i]]=k;34             if (k>0) k--;35         }36     }37 }38 void work()39 {40     p=0,q=1;41     for (int i=1; i<=n; i++) v[a[i]]++;42     for (int i=1; i<=30; i++) v[i]+=v[i-1];43     for (int i=1; i<=n; i++) sa[p][v[a[i]]--]=i;44     for (int i=1; i<=n; i++) rank[p][sa[p][i]]=rank[p][sa[p][i-1]]+(a[sa[p][i]]!=a[sa[p][i-1]]);45     for (k=1; k