suffix array O ( N log N ) + lcp

void make(vector <int> &suf, vector <int> &cls, string s) {
    vector <pair<char, int>> ord;
    for (int i = 0; i < s.size(); ++i) {
        ord.push_back(make_pair(s[i], i));
    }
    int cur = -1;
    char prev = '0';
    sort(ord.begin(), ord.end());
    int j = 0;
    for (auto i : ord) {
        suf[j++] = i.second;
        if (i.first != prev) {
            cur++;
        }
        cls[i.second] = cur;
        prev = i.first;
    }
}

vector <int> suffix_array(string s) {
    s = s + '#';
    int n = s.size();
    vector <int> suf(n), cls(n);
    make(suf, cls, s);
    int l = 0;
    while ((1 << l) < n) {
        vector <int> nowsort;
        for (int i = 0; i < n; ++i) {
            int cur = suf[i];
            int id = (cur - (1 << l) + n) % n;
            nowsort.push_back(id);
        }
        vector <int> beg(n), cnt(n);
        for (int i = 0; i < n; ++i) {
            cnt[cls[i]]++;
        }
        for (int i = 1; i < n; ++i) {
            beg[i] += beg[i - 1] + cnt[i - 1];
        }
        for (int i = 0; i < n; ++i) {
            int f = cls[nowsort[i]];
            suf[beg[f]++] = nowsort[i];
        }
        pair <int, int> prev = {-1, -1};
        int cur = -1;
        vector <int> newcls(n);
        for (int i = 0; i < n; ++i) {
            int ct = suf[i];
            pair <int, int> F = {cls[ct], cls[(ct + (1 << l)) % n]};
            if (F != prev) {
                cur++;
            }
            newcls[suf[i]] = cur;
            prev = F;
        }
        cls = newcls;
        l++;
    }
    vector <int> ans(n - 1);
    for (int i = 0; i < n - 1; ++i)
        ans[i] = suf[i + 1];
    return ans;
}

vector <int> getLcp(vector <int> &suf, string s) {
    int n = suf.size();
    vector <int> pos(n);
    for (int i = 0; i < suf.size(); ++i)
        pos[suf[i]] = i;
    vector <int> lcp(n);
    for (int i = 0; i < n; i++) {
        if (pos[i] == n - 1) continue;
        int z = 0;
        if (i > 0 && pos[i - 1] != n - 1 && lcp[pos[i - 1]] > 0)
            z = lcp[pos[i - 1]] - 1;
        while (i + z < n && suf[pos[i] + 1] + z < n && s[i + z] == s[suf[pos[i] + 1] + z]) z++;
        lcp[pos[i]] = z;
    }
    int res = 0;
    for (int i = 1; i < n; i++) {
        res += n - suf[i] - lcp[i] - 1;
    }
    return lcp;
}