1 int sa[MAX],temp[MAX],rank[MAX];
 2 int n,k;
 3 bool cmp_sa(int i,int j) {
 4     if(rank[i]!=rank[j]) return rank[i]<rank[j];
 5     else {
 6         int ri= i+k<=n ? rank[i+k] : -1;
 7         int rj= j+k<=n ? rank[j+k] : -1;
 8         return ri<rj;
 9     }
10 }
11 void construct_sa(string S,int *sa) {
12     n=S.size();
13     for(int i=0;i<=n;i++) {
14         sa[i]=i;
15         rank[i]= i < n ? S[i] : -1;
16     }
17     for(k=1;k<=n;(k<<=1)) {
18         sort(sa,sa+1+n,cmp_sa) ;
19         temp[sa[0]]=0;
20         for(int i=1;i<=n;i++) {
21             temp[sa[i]]=temp[sa[i-1]]+(cmp_sa(sa[i-1],sa[i])? 1 : 0);
22         }
23         for(int i=0;i<=n;i++) {
24             rank[i]=temp[i];
25         }
26     }