后缀数组 Manber-Myers 算法是基于倍增思想的

class suffixArray {
public:
    int str[maxn], sa[maxn];
    int c[maxn], t1[maxn], t2[maxn];

    int n;

    void build(int R) {
        *x = t1, *y = t2;

        // radix sort according to 1stKey
        _for(i, 0, R) c[i] = 0;
        _for(i, 0, n) c[x[i] = str[i]]++;
        _for(i, 1, R) c[i] += c[i - 1];
        _forDown(i, n - 1, 0) sa[--c[x[i]]] = i;

        // manber-myers loop
        for(int k = 1; k <= n; k <<= 1) {
            // construct y[], use sa[] to construct 2ndKey
            int p = 0;
            _for(i, n-k, n) y[p++] = i;
            _for(i, 0, n) if(sa[i] >= k) y[p++] = sa[i] - k;

            // radix sort y[], according to (1st, 2nd) key
            _for(i, 0, R) c[i] = 0;
            _for(i, 0, n) c[x[y[i]]]++;
            _for(i, 1, R) c[i] += c[i - 1];
            _forDown(i, n - 1, 0) sa[--c[x[y[i]]]] = y[i];
        }

        // update x[] and loop
        swap(x, y);
        x[sa[0]] = 0;

        p = 1;
        _for(i, 1, n) {
            bool flag = (x[sa[i]] == x[sa[i - 1]] && x[sa[i]+k] == x[sa[i-1]+k]);
            x[sa[i]] = (flag ? p - 1 : p++);
        }

        // update p and R
        if(p >= n) break;
        R = p;
    }
};