后缀数组(Suffix Array)实现与LCP计算

//<cmath> <vector> <algorithm>
struct suffix_array {
    static const int max_val = 0xff;
    static const int max_n = 0xffff;
    int index[max_n], rank[max_n];
    int cnt[max_n], buf1[max_n], buf2[max_n];
    int lcp[max_n], min_lcp[max_n][0xf];
    void build(const char* str, int n, int m = max_val) {
        int *x = buf1, *y = buf2;
        fill(cnt, cnt + m, 0);
        for (int i = 0; i < n; ++i)
            ++cnt[x[i] = str[i]];
        for (int i = 1; i < m; ++i)
            cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; --i)
            index[--cnt[x[i]]] = i;
        for (int i = 1; ; i *= 2) {
            int p = 0;
            for (int j = n - i; j < n; ++j)
                y[p++] = j;
            for (int j = 0; j < n; ++j)
                if (index[j] >= i)
                    y[p++] = index[j] - i;
            fill(cnt, cnt + m, 0);
            for (int j = 0; j < n; ++j)
                ++cnt[x[j]];
            for (int j = 1; j < m; ++j)
                cnt[j] += cnt[j - 1];
            for (int j = n - 1; j >= 0; --j)
                index[--cnt[x[y[j]]]] = y[j];