个人后缀数组模板分享
感觉目前大多模板都是一种格式，但是个人习惯了0-index和区间左闭右开,很不习惯字符串的算法是1-index,所以也只能理解后自己写个模板供自己使用，在这里，如果有和本人相同习惯的人，希望分享学习交流，这里分享自己的后缀数组代码，希望诸位大佬看了本人代码也稍微嘴下留情。如果能让1-index的同学也能学到点东西的话我也不胜荣幸。

//sa数组排名也是从0开始的 
struct SuffixArray {
    static const int N = 1e6;
    int n, m;
    int sa[N], hgt[N], rk[N], x[N], y[N], p[N + 1], c[N];
    SuffixArray(const string &s) : n(s.size()), m(max(n, 'z' + 1)) {
        for(int i = 0; i < n; i++) x[i] = s[i], y[i] = i;
        rSort();
        for(int k = 1; k <= n; k <<= 1) {
            int cur = 0;
            for(int i = n - k; i < n; i++) y[cur++] = i;
            for(int i = 0; i < n; i++)
                if(sa[i] >= k) y[cur++] = sa[i] - k;
            rSort();
            rk[sa[0]] = cur = 0;
            for(int i = 1; i < n; i++) {
                int a = sa[i], b = sa[i - 1];
                if(a >= n - k || b >= n - k || x[a] != x[b] || x[a + k] != x[b + k]) cur++;
                rk[a] = cur;
            }
            if(cur == n - 1) break;
            swap(x, rk);
            m = ++cur;
        }
        for(int i = 0, k = 0; i < n; i++) {
            if(!rk[i]) continue;
            if(k) k--;
            int j = sa[rk[i] - 1];
            while(i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
            hgt[rk[i]] = k;
        }
    }
    void rSort() {
        for(int i = 0; i < n; i++) c[x[i]]++;
        for(int i = 1; i <= m; i++) p[i] = p[i - 1] + c[i - 1], c[i - 1] = 0;
        for(int i = 0; i < n; i++) sa[p[x[y[i]]]++] = y[i];
        p[0] = 0;
    }
};