1698. Number of Distinct Substrings in a String

Given a string s, return the number of distinct substrings of s.

A substring of a string is obtained by deleting any number of characters (possibly zero) from the front of the string and any number (possibly zero) from the back of the string.

c++

class Solution {
    vector<int> sa, g, tg, lcp, rsa;
    int t, n;
    void suffixArray(string& s) {
        t = 1, n = s.length();
        sa = vector<int>(n);
        tg = vector<int>(n + 1);
        g = vector<int>(n + 1);

        for(int i = 0; i < n; i++) {
            sa[i] = i;
            g[i] = s[i] - 'a';
        }

        while(t <= n) {
            g[n] = -1;
            auto compare = [g = g, t = t](int x, int y) {
                if(g[x] == g[y])
                    return g[x + t] < g[y + t];
                return g[x] < g[y];
            };
            sort(begin(sa), end(sa), compare);
            tg[sa[0]] = 0;
            for(int i = 1; i < n; i++)
                tg[sa[i]] = tg[sa[i-1]] + compare(sa[i-1],sa[i]);
            g = tg;
            t<<=1;
        }
    }
    void longestCommonPrefix(string& s) {
        suffixArray(s);
        lcp = vector<int>(n);
        rsa = vector<int>(n);
        for(int i = 0; i < n; i++)
            rsa[sa[i]] = i;
        int len = 0;
        for(int i = 0; i < n; i++) {
            int k = rsa[i];
            if(k) {
                int j = sa[k-1];
                while(s[i+len] == s[j+len]) len++;
                lcp[k] = len;
                if(len) --len;
            }
        }
    }
public:
    int countDistinct(string s) {
        longestCommonPrefix(s);
        return n * (n + 1) / 2 - accumulate(begin(lcp),end(lcp),0);
    }
};