代码

// 1006: suffix array + LCP, n <= 1e5, lowercase string.
#include <cstdio>
#include <cstring>

static const int MAXN = 100005;
static int sa_[MAXN], rnk[MAXN], lcp[MAXN];

static int ARENA[1 << 21];
static int *asp = ARENA;
static inline int *alloc_ints(int cnt) { int *p = asp; asp += cnt; return p; }

template <class T>
static void induce(const T *s, int *sa, int n, const char *ls, const int *sum_l,
                   const int *sum_s, int upper, const int *src, int srclen, int *buf) {
    memset(sa, 0xff, sizeof(int) * (size_t)n);
    for (int i = 0; i <= upper; i++) buf[i] = sum_s[i];
    for (int i = 0; i < srclen; i++) { int d = src[i]; if (d == n) continue; sa[buf[s[d]]++] = d; }
    for (int i = 0; i <= upper; i++) buf[i] = sum_l[i];
    sa[buf[s[n - 1]]++] = n - 1;
    for (int i = 0; i < n; i++) {
        int v = sa[i];
        if (v >= 1 && !ls[v - 1]) sa[buf[s[v - 1]]++] = v - 1;
    }
    for (int i = 0; i <= upper; i++) buf[i] = sum_l[i];
    for (int i = n - 1; i >= 0; i--) {
        int v = sa[i];
        if (v >= 1 && ls[v - 1]) sa[--buf[s[v - 1] + 1]] = v - 1;
    }
}

template <class T>
static void sa_is(const T *s, int *sa, int n, int upper) {
    if (n == 1) { sa[0] = 0; return; }
    if (n == 2) { if (s[0] < s[1]) { sa[0] = 0; sa[1] = 1; } else { sa[0] = 1; sa[1] = 0; } return; }
    int *save = asp;
    char *ls = (char *)alloc_ints((n + 3) / 4 + 1);
    int *sum_l = alloc_ints(upper + 2);
    int *sum_s = alloc_ints(upper + 2);
    int *buf = alloc_ints(upper + 2);
    int *lms = alloc_ints(n / 2 + 2);
    int *lms_map = alloc_ints(n + 1);
    int *sorted_lms = alloc_ints(n / 2 + 2);
    int *rec_s = alloc_ints(n / 2 + 2);
    int *rec_sa = alloc_ints(n / 2 + 2);

    for (int i = n - 2; i >= 0; i--)
        ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1] ? 1 : 0);
    for (int i = 0; i <= upper; i++) { sum_l[i] = 0; sum_s[i] = 0; }
    for (int i = 0; i < n; i++) {
        if (!ls[i]) sum_s[s[i]]++;
        else sum_l[s[i] + 1]++;
    }
    for (int i = 0; i <= upper; i++) {
        sum_s[i] += sum_l[i];
        if (i < upper) sum_l[i + 1] += sum_s[i];
    }
    int m = 0;
    for (int i = 0; i <= n; i++) lms_map[i] = -1;
    for (int i = 1; i < n; i++) if (!ls[i - 1] && ls[i]) { lms_map[i] = m; lms[m++] = i; }

    induce(s, sa, n, ls, sum_l, sum_s, upper, lms, m, buf);
    if (m == 0) { asp = save; return; }

    int cnt = 0;
    for (int i = 0; i < n; i++) if (sa[i] >= 0 && lms_map[sa[i]] != -1) sorted_lms[cnt++] = sa[i];
    int rec_upper = 0;
    rec_s[lms_map[sorted_lms[0]]] = 0;
    for (int i = 1; i < m; i++) {
        int l = sorted_lms[i - 1], r = sorted_lms[i];
        int end_l = (lms_map[l] + 1 < m) ? lms[lms_map[l] + 1] : n;
        int end_r = (lms_map[r] + 1 < m) ? lms[lms_map[r] + 1] : n;
        bool same = true;
        if (end_l - l != end_r - r) same = false;
        else {
            while (l < end_l) { if (s[l] != s[r]) break; l++; r++; }
            if (l == n || s[l] != s[r]) same = false;
        }
        if (!same) rec_upper++;
        rec_s[lms_map[sorted_lms[i]]] = rec_upper;
    }
    if (rec_upper + 1 == m) {
        for (int i = 0; i < m; i++) rec_sa[rec_s[i]] = i;
    } else {
        sa_is(rec_s, rec_sa, m, rec_upper);
    }
    for (int i = 0; i < m; i++) sorted_lms[i] = lms[rec_sa[i]];
    induce(s, sa, n, ls, sum_l, sum_s, upper, sorted_lms, m, buf);
    asp = save;
}

static char outbuf[1 << 22];

static const char DIG[201] =
    "00010203040506070809" "10111213141516171819" "20212223242526272829"
    "30313233343536373839" "40414243444546474849" "50515253545556575859"
    "60616263646566676869" "70717273747576777879" "80818283848586878889"
    "90919293949596979899";

static inline char *writeInt(char *p, unsigned v) {
    if (v < 100) {
        if (v < 10) *p++ = char('0' + v);
        else { *p++ = DIG[2 * v]; *p++ = DIG[2 * v + 1]; }
        return p;
    }
    unsigned r = v % 100; v /= 100;
    if (v < 100) {
        if (v < 10) *p++ = char('0' + v);
        else { *p++ = DIG[2 * v]; *p++ = DIG[2 * v + 1]; }
        *p++ = DIG[2 * r]; *p++ = DIG[2 * r + 1];
        return p;
    }
    unsigned r2 = v % 100; v /= 100;
    if (v >= 10) { *p++ = DIG[2 * v]; *p++ = DIG[2 * v + 1]; }
    else *p++ = char('0' + v);
    *p++ = DIG[2 * r2]; *p++ = DIG[2 * r2 + 1];
    *p++ = DIG[2 * r]; *p++ = DIG[2 * r + 1];
    return p;
}

int main() {
    static unsigned char str[MAXN];
    int len = (int)fread(str, 1, MAXN - 2, stdin);
    while (len > 0 && (str[len - 1] == '\n' || str[len - 1] == '\r' || str[len - 1] == ' ')) len--;
    int n = len;
    static unsigned char s0[MAXN];
    s0[0] = 0;
    for (int i = 1; i <= n; i++) s0[i] = (unsigned char)(str[i - 1] - 'a' + 1);
    sa_is(s0, sa_, n + 1, 27);
    for (int i = 0; i < n; i++) sa_[i] = sa_[i + 1];
    for (int i = 0; i < n; i++) rnk[sa_[i]] = i;
    int k = 0;
    lcp[0] = 0;
    const int PF = 12;
    for (int i = 1; i <= n; i++) {
        if (i + PF <= n) __builtin_prefetch(&sa_[rnk[i + PF] + 1]);
        int r = rnk[i];
        if (r == n - 1) { k = 0; continue; }
        int j = sa_[r + 1];
        while (i + k <= n && j + k <= n && s0[i + k] == s0[j + k]) k++;
        lcp[r + 1] = k;
        if (k) k--;
    }
    char *p = outbuf;
    for (int i = 0; i < n; i++) { if (i) *p++ = ' '; p = writeInt(p, sa_[i]); }
    *p++ = '\n';
    for (int i = 1; i < n; i++) { if (i > 1) *p++ = ' '; p = writeInt(p, lcp[i]); }
    *p++ = '\n';
    fwrite(outbuf, 1, p - outbuf, stdout);
    return 0;
}

评测结果