Suffix Array

struct Entry {
    int first;
    int second;
    int p;

    bool operator <(const Entry& e) const {
        return (first == e.first ? second < e.second : first < e.first);
    }
} L[SIZE];

int P[MAX_LOG][SIZE];
int LCP[SIZE];
int step;
int B[SIZE];

bool comp(const int& a, const int& b) {
    return P[step - 1][a] < P[step - 1][b];
}

void suffixArray(string &str) {
    int i, cnt;

    for (i = 0; i < str.size(); i++)
        P[0][i] = str[i] - 'a';

    for (step = 1, cnt = 1; (cnt>>1) < str.size(); step++, cnt <<= 1) {
        for (i = 0; i < str.size(); i++) {
            L[i].first = P[step - 1][i];
            L[i].second = (i + cnt < str.size() ? P[step - 1][i + cnt] : -1);
            L[i].p = i;
        }

        sort(L, L + str.size());

        for (i = 0; i < str.size(); i++) {
            P[step][L[i].p] =
                (i > 0 && L[i].first == L[i - 1].first && L[i].second == L[i - 1].second
                    ? P[step][L[i - 1].p] : i);
        }
    }

    for (i = 0; i < str.size(); i++)
        B[i] = i;
    sort(B, B + str.size(), comp);

    for (i = 1; i < str.size(); i++) {
        int k;
        int x = B[i];
        int y = B[i - 1];

        LCP[i] = 0;
        for (k = step - 1; k >= 0 && x < str.size() && y < str.size(); k--) {
            if (P[k][x] == P[k][y]) {
                x += 1 << k;
                y += 1 << k;
                LCP[i] += 1 << k;
            }
        }
    }

    /*for (i = 0; i < str.size(); i++)
        cout << B[i] << " : " << LCP[i] << endl;*/
}

int main()
{
    int tc, t, x, y, z, d;
    int i, j, k, l, h, n, m;
    char ch; double P;
    string str, str1, str2;

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif

    ios_base::sync_with_stdio(false);

    cin >> str;
    suffixArray(str);

    int total = 0;
    for (i = 0; i < str.size(); i++)
        total += (str.size() - B[i] - LCP[i]);
    cout << total << endl;

    return 0;
}