代码

    #include <bits/stdc++.h>

    using namespace std;

    class SuffixArray {
    public:
        using size_type = unsigned;
        using pointer = size_type*;
        using const_pointer = const size_type*;

    private:
        inline static bool is_negative(size_type n) noexcept {
            return (typename std::make_signed<size_type>::type)(n) < 0;
        }

        template<typename It>
        inline static void get_sbuk(It s, pointer sbuk, size_type n, size_type m) noexcept(noexcept(s[0])) {
            std::fill_n(sbuk, m, 0);

            for (size_type i = 0; i < n; ++i)
                ++sbuk[s[i]];

            std::partial_sum(sbuk, sbuk + m, sbuk);
        }

        inline static void lbuk_to_sbuk(const_pointer lbuk, pointer sbuk, size_type n, size_type m) noexcept {
            std::copy_n(lbuk + 1, m - 1, sbuk);
            sbuk[m - 1] = n;
        }

        inline static void sbuk_to_lbuk(pointer lbuk, const_pointer sbuk, size_type n, size_type m) noexcept {
            lbuk[0] = 0;
            std::copy_n(sbuk, m - 1, lbuk + 1);
        }

        template<typename It>
        static size_type fill_lms_char(It s, pointer sa, pointer sbuk, size_type n,
                                    size_type m) noexcept(noexcept(s[0])) {
            using value_type = typename std::iterator_traits<It>::value_type;
            value_type pre, cur = s[n - 1];
            value_type c = m - 1;
            size_type n0 = 0;
            std::fill_n(sa, n, 0);

            for (size_type j = 0, i = n - 1; i > 0;) {
                do
                    pre = cur;

                while (!is_negative(--i) && (cur = s[i]) >= pre);

                if (is_negative(i))
                    break;

                do
                    pre = cur;

                while (!is_negative(--i) && (cur = s[i]) <= pre);

                if (is_negative(i))
                    break;

                sa[--sbuk[c]] = j;
                j = i + 1;
                c = pre;
                ++n0;
            }

            return n0;
        }

        template<typename It>
        static void fill_lms_suffix(It s, pointer sa, const_pointer sbuk, size_type n, size_type m,
                                    size_type n0) noexcept(noexcept(s[0])) {
            using value_type = typename std::iterator_traits<It>::value_type;

            if (n0 == 0)
                return;

            size_type p = sa[n0 - 1];
            value_type pre, cur = s[p];
            size_type i = n0 - 1, j = n;

            do {
                for (const size_type k = sbuk[pre = cur]; j > k;)
                    sa[--j] = 0;

                do
                    sa[--j] = p;

                while (!is_negative(--i) && (cur = s[p = sa[i]]) == pre);
            } while (!is_negative(i));

            while (j > 0)
                sa[--j] = 0;
        }

        template<typename It>
        static size_type induce_and_rename_lms_substr(It s, pointer sa, pointer s0, pointer lbuk, pointer sbuk,
                pointer time, size_type n, size_type m, size_type n0) noexcept(noexcept(s[0])) {
            using value_type = typename std::iterator_traits<It>::value_type;

            for (size_type i = 1; i < m; ++i)
                if (sbuk[i - 1] != lbuk[i])
                    sa[sbuk[i - 1]] = ~sa[sbuk[i - 1]];

            lbuk_to_sbuk(lbuk, sbuk, n, m);
            value_type pre = s[n - 1], cur;
            pointer ptr = sa + lbuk[pre];
            *ptr++ = ~(n - 1);
            bool inc = false;
            size_type cnt = 0;
            std::fill_n(time, m, 0);

            for (size_type p, i = 0; i < n; ++i) {
                if ((p = sa[i]) == 0)
                    continue;

                const bool b = is_negative(p);

                if (b) {
                    ++cnt;
                    p = ~p;
                }

                if ((cur = s[p - 1]) < s[p]) {
                    if (inc) {
                        inc = false;
                        sa[i] = ~p;
                    }

                    continue;
                }

                --p;
                inc |= b;
                sa[i] = 0;

                if (cur != pre) {
                    lbuk[pre] = ptr - sa;
                    ptr = sa + lbuk[pre = cur];
                }

                if (time[cur] != cnt) {
                    time[cur] = cnt;
                    p = ~p;
                }

                *ptr++ = p;
            }

            for (size_type p, i = n; i-- > 0;) {
                if (is_negative((p = sa[i]) - 1))
                    continue;

                sa[i] = ~p;

                while (!is_negative(p = sa[--i]));

                sa[i] = ~p;
            }

            ptr = sa + sbuk[pre = 0];
            sbuk_to_lbuk(lbuk, sbuk, n, m);

            for (size_type p, i = n; i-- > 0;) {
                if ((p = sa[i]) == 0)
                    continue;

                const bool b = is_negative(p);

                if (b) {
                    ++cnt;
                    p = ~p;
                }

                if ((cur = s[p - 1]) > s[p]) {
                    if (inc) {
                        inc = false;
                        sa[i] = ~p;
                    }

                    continue;
                }

                --p;
                inc |= b;
                sa[i] = 0;

                if (cur != pre) {
                    sbuk[pre] = ptr - sa;
                    ptr = sa + sbuk[pre = cur];
                }

                if (time[cur] != cnt) {
                    time[cur] = cnt;
                    p = ~p;
                }

                *--ptr = p;
            }

            size_type m0 = 0;

            for (size_type p, j = 0, i = 0; j < n0; ++i) {
                if ((p = sa[i]) != 0) {
                    sa[i] = 0;
                    sa[j++] = p;
                    m0 += is_negative(p);
                }
            }

            if (m0 == n0) {
                for (size_type i = 0; i < n0; ++i)
                    sa[i] = ~sa[i];
            } else {
                for (size_type p, j = m0 + 1, i = n0; i-- > 0;) {
                    if (is_negative(p = sa[i])) {
                        p = ~p;
                        --j;
                    }

                    sa[n0 + p / 2] = j;
                }

                for (size_type p, j = n0, i = n0 + n / 2 - 1; j > 0; --i)
                    if ((p = sa[i]) != 0)
                        s0[--j] = p - 1;
            }

            return m0;
        }

        template<typename It>
        static void induce_suffix(It s, pointer sa, pointer lbuk, pointer sbuk, size_type n,
                                size_type m) noexcept(noexcept(s[0])) {
            using value_type = typename std::iterator_traits<It>::value_type;
            value_type pre = s[n - 1], cur;
            pointer ptr = sa + lbuk[pre];
            *ptr++ = n - 1;

            for (size_type p, i = 0; i < n; ++i) {
                if ((p = sa[i]) == 0)
                    continue;

                if ((cur = s[p - 1]) < s[p]) {
                    sa[i] = ~p + 1;
                    continue;
                }

                if (cur != pre) {
                    lbuk[pre] = ptr - sa;
                    ptr = sa + lbuk[pre = cur];
                }

                *ptr++ = p - 1;
            }

            ptr = sa + sbuk[pre = 0];

            for (size_type p, i = n; i-- > 0;) {
                if (is_negative(p = ~sa[i]))
                    continue;

                if ((cur = s[p]) > s[sa[i] = p + 1])
                    continue;

                if (cur != pre) {
                    sbuk[pre] = ptr - sa;
                    ptr = sa + sbuk[pre = cur];
                }

                *--ptr = ~p + 1;
            }
        }

        template<typename It>
        static void sais(It s, pointer sa, size_type n, size_type m, size_type r, pointer buf, size_type buf_size) {
            using value_type = typename std::iterator_traits<It>::value_type;

            size_type used_sa[2] = {}, used_buf[2] = {}, used_nbuf[2] = {};
            const auto divide = [](size_type n, size_type m) {
                return 2 * m <= n ? 3 * m <= n ? 3 : 2 : m <= n ? 1 : 0;
            };
            const size_type cnt_sa = divide(r, m), cnt_buf = divide(buf_size, m);
            const size_type nbuf_size = cnt_sa + cnt_buf < 3 ? (3 - cnt_sa - cnt_buf) * m : 0;
            const pointer nbuf = nbuf_size > 0 ? new size_type[nbuf_size] : nullptr;
            std::unique_ptr<size_type[]> nbuf_guard(nbuf);
            const pointer rsa = sa + n + r - m;
            const auto alloc = [&](bool reusable) {
                if (used_sa[0] + used_sa[1] + m <= r) {
                    const pointer ans = rsa - used_sa[0] - used_sa[1];
                    used_sa[reusable] += m;
                    return ans;
                }

                if (used_buf[0] + used_buf[1] + m <= buf_size) {
                    const pointer ans = buf + used_buf[0] + used_buf[1];
                    used_buf[reusable] += m;
                    return ans;
                }

                if (used_nbuf[0] + used_nbuf[1] + m <= nbuf_size) {
                    const pointer ans = nbuf + used_nbuf[0] + used_nbuf[1];
                    used_nbuf[reusable] += m;
                    return ans;
                }

                return pointer(nullptr);
            };
            const pointer lbuk = alloc(false), sbuk = alloc(true), time = alloc(true);

            get_sbuk(s, sbuk, n, m);
            sbuk_to_lbuk(lbuk, sbuk, n, m);
            const size_type n0 = fill_lms_char(s, sa, sbuk, n, m);

            if (n0 > 0) {
                const size_type nr = n + r - 2 * n0 - used_sa[0];
                const pointer sa0 = sa, s0 = sa + nr + n0;
                const size_type m0 = induce_and_rename_lms_substr(s, sa, s0, lbuk, sbuk, time, n, m, n0);

                if (m0 < n0) {
                    if (buf_size - used_buf[0] > nbuf_size - used_nbuf[0])
                        sais(s0, sa0, n0, m0, nr, buf + used_buf[0], buf_size - used_buf[0]);
                    else
                        sais(s0, sa0, n0, m0, nr, nbuf + used_nbuf[0], nbuf_size - used_nbuf[0]);

                    value_type pre, cur = s[n - 1];

                    for (size_type j = n0, i = n - 1; i > 0;) {
                        do
                            pre = cur;

                        while (!is_negative(--i) && (cur = s[i]) >= pre);

                        if (is_negative(i))
                            break;

                        do
                            pre = cur;

                        while (!is_negative(--i) && (cur = s[i]) <= pre);

                        if (is_negative(i))
                            break;

                        s0[--j] = i + 1;
                    }

                    for (size_type i = 0; i < n0; ++i)
                        sa0[i] = s0[sa0[i]];
                }
            }

            lbuk_to_sbuk(lbuk, sbuk, n, m);
            fill_lms_suffix(s, sa, sbuk, n, m, n0);
            induce_suffix(s, sa, lbuk, sbuk, n, m);
        }

    public:
        template<typename It>
        static void suffix_sort(It s, pointer sa, size_type n, size_type m, pointer buf = nullptr,
                                size_type buf_size = 0) {
            if (n > 0)
                sais(s, sa, n, m, 0, buf, buf_size);
        }
    };

    char s[1000001];
    unsigned sa[1000000];
    unsigned buf[1722224];

    int main() {
        const unsigned n = fread(s, 1, 1000000, stdin), m = 128;
        SuffixArray::suffix_sort(s, sa, n, m, buf, 1722224);
        char *ans = reinterpret_cast<char *>(buf);
        char *cur = ans;

        for (unsigned i = 0; i < n; ++i) {
            char stk[7];
            char *top = stk;

            for (unsigned j = sa[i] + 1; j > 0; j /= 10)
                * top++ = j % 10 + '0';

            switch (top - stk) {
            case 7:
                *cur++ = stk[6];

            case 6:
                *cur++ = stk[5];

            case 5:
                *cur++ = stk[4];

            case 4:
                *cur++ = stk[3];

            case 3:
                *cur++ = stk[2];

            case 2:
                *cur++ = stk[1];

            case 1:
                *cur++ = stk[0];
                *cur++ = ' ';
            }
        }

        fwrite(ans, 1, cur - ans, stdout);
    return 0;
}

评测结果