String

Suffix array

Linear time suffix array construction

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin >> s;
    int n = (int)s.size();
    suffix_array sa(s);
    sa.run('a', 'z');
    for (int i = 0; i < n; i++) {
        cout << sa.sa[i] + 1 << " \n"[i == n - 1];
    }
    cout << "x";
    for (int i = 0; i < n - 1; i++) {
        cout << " " << sa.lcp[i];
    }
    cout << "\n";
    return 0;
}