倍增算法

namespace suffix_array{
    int sa[maxn], rak[maxn]; 
    //sa[i] 排名为i的后缀的起始下标 
    //rak[i] 起始下标为i的后缀的排名
    int cnt[maxn], pos[maxn];
    int height[maxn];

    void getHeight(const string &str, int n){
        int k = 0;
        for(int i = 1; i <= n; i++) rak[sa[i]] = i;
        for(int i = 1; i <= n; i++){
            if(rak[i] == 1)    continue;
            if(k) k--;
            int j = sa[rak[i]-1];
            while(j+k-1 < n && i+k-1 < n && str[i+k-1] == str[j+k-1])    k++;
            height[rak[i]] = k;
        }
        return;
    }

    void getSA(const string &str, int n, int m = 130){//n为字符串长度 
        for(int i = 1; i <= m; i++)    cnt[i] = 0;
        for(int i = 1; i <= n; i++)    cnt[rak[i] = str[i-1] - '\0']++;
        for(int i = 1; i <= m; i++)    cnt[i] += cnt[i-1];
        for(int i = n; i >= 1; i--)    sa[cnt[rak[i]]--] = i;
        for(int k = 1, p = 0; p < n && k < n; k <<= 1, m = p, p = 0){
            for(int i = n - k + 1; i <= n; i++)    pos[++p] = i;
            for(int i = 1; i <= n; i++){
                if(sa[i] > k)    pos[++p] = sa[i] - k;
            } 
            for(int i = 0; i <= m; i++)    cnt[i] = 0;
            for(int i = 1; i <= n; i++)    cnt[rak[i]]++;
            for(int i = 1; i <= m; i++)    cnt[i] += cnt[i-1];
            for(int i = n; i >= 1; i--)    sa[cnt[rak[pos[i]]]--] = pos[i];
            for(int i = 1; i <= n; i++)    pos[i] = rak[i];
            p = 1; rak[sa[1]] = 1;
            for(int i = 2; i <= n; i++){
                if(pos[sa[i]] != pos[sa[i-1]] || pos[sa[i]+k] != pos[sa[i-1]+k])    p++;
                rak[sa[i]] = p;
            }
        }
        return;
    }
}