include<stdio.h>
include<string.h>
include<iostream>
using namespace std;
define MAXN   123123
char s[MAXN];
int sa[MAXN],t[MAXN],t2[MAXN],c[MAXN],n;
void build(int m)
{

int i,*x=t,*y=t2;

//其實下面的是計數排序

for(i=0;i<m;i++) c[i]=0;

for(i=0;i<n;i++) c[x[i]=s[i]]++;

for(i=0;i<m;i++) c[i]+=c[i-1];//其實這個時候每個數的名次已經有了

for(i=n-1;i>=0;i--)  sa[--c[x[i]]]=i;

/*最后一個for循環可能感覺莫名其妙可以改成下面兩個for循環可能就很容易的看出來了

for(i=n-1;i>=0;i--)

    rank[i]=--c[x[x[i]]];

for(i=n-1;i>=0;i--)

    sa[rank[i]]=i;

根據sa[rank[i]]=i這個定理把rank[i]為--c[x[x[i]]]所以把--c[x[x[i]]]帶入第二個

for循環就化為了上面計數排序的最后一個for循環

*/

for(int k=1;k<=n;k<<=1/*和k=k*2等價*/)

{

    int p=0;

    /*直接利用sa數組排序第二關鍵字也就是相當于一個兩位數的個位數，y保存的是第二關鍵字

    的sa[i]的值

    */

    for(i=n-k;i<n;i++)

        y[p++]=i;/*因為第二關鍵字超范圍，看做小于所有的第二關鍵字，所以他們的排名

        rank[n-k]...rank[n-1]的排名為0,1,2,....所以y[rank[n-k]]...y[rank[n-1]]的值位n-k...n-1

        根據sa[rank[i]]=i;化簡得rank[0]..rank[k]的值為n-k...n-1

    */

    for(i=0;i<n;i++)

        if(sa[i]>=k) y[p++]=sa[i]-k;

    /*因為這是排的第二關鍵字，當位于最后的后綴可能已經沒有第二個已經沒有第二個關鍵字了

      這個時候就把這樣的關鍵字都初始化為小于所有的第二關鍵字，而且，suffix(sa[0])<=suffix(sa[1])..

      當我們排第二關鍵字的時候第一關鍵字已經沒有用了，換句話說，前k個我們已經用不到了，也就是

      下標小于k的，也就是sa[i]小于k的，舉個例子baba這個字符串第一次算出來的sa數組為1 3 0 2，也就是

      suffix(1)<=suffix(3)<=suffix(0)<suffix(2)也就是a<=a<=b<=b而第二關鍵字為aba@這個@是小于所有的

      字符，而第一個a就沒有用了，也就是sa[k]=0的就沒有用了，因為sa[k]表示的是以0首字符為下標的

      的排名為k這個時候我們已經不再需要排小于k的下標了，但去掉小于k的sa[]后他們的sa[]的值是相對的

      如去掉0以后就剩下132了因為去掉了1個所以所有大于等于1的都得減1，同理，去掉k個就得減去k個

    */

    //基數排序第一個關鍵字x數組存的是相當于rank[],且y[i]相當于與第一關鍵字，可以手動模擬一下baba

    for(i=0;i<m;i++) c[i]=0;

    for(i=0;i<n;i++) c[x[y[i]]]++;

    for(i=0;i<m;i++) c[i]+=c[i-1];

    for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];

    /*

    可以換成下面的for更直觀一些rank1記錄的是rank的值,把y[i]看成一個下標

    for(i=0;i<m;i++) 

        rank[i]=x[y[i]];

    for(i=0;i<n;i++) c[i]=0;

    for(i=0;i<m;i++)

        c[rank[i]]++;

    for(i=0;i<m;i++)  c[i]+=c[i-1];

    for(i=n-1;i>=0;i--)

        rank1[y[i]]==--c[x[y[i]]];

    for(i=n-1;i>=0;i--)

        sa[rank1[y[i]]]=y[i];

    把rank1=--c[x[y[i]]]帶入得sa[--c[x[y[i]]]]=y[i];

    這個時候sa數組存的已經是倍增后的值但是這個時候rank[sa[i]]=i還不一定成立所以需要在下面進行驗證

    */

    //根據sa和y數組計算新的x數組（這時說的y是x數組和y數組交換后的y數組也就相當于rank數組）

    swap(x,y);

    p=1;x[sa[0]]=0;

    for(i=1;i<n;i++)

        x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;

    if(p>=n) break;

    m=p;

    /*

    如果r[sa[i-1]]==r[sa[i]],那么，說明在以a,b為開始的l長度的字符串內肯定不包括@（這也是最后

    一個元素給@的原因），所以sa[i-1]+k,sa[i]+k都小于n-k，所以此處數組不會越界。若果不相等那么

    根據&&的短路特性后邊的sa[i]+k就不會判斷了

    */

}


}
int main()
{

return 0;


}
/*
dcba
aabb
baba
bababa
bbaa
aaab
*/
</pre>