代码

// 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 char s_[MAXN];

// arena for recursion scratch
static int ARENA[1 << 21];
static int *asp = ARENA;

static inline int *alloc_ints(int cnt) { int *p = asp; asp += cnt; return p; }

static void induce(const int *s, int *sa, int n, char *ls, const int *sum_l, const int *sum_s,
                   int upper, const int *src, int srclen, int *buf) {
    for (int i = 0; i < n; i++) sa[i] = -1;
    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; }
}

static void sa_is(const int *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 char *op = outbuf;

static inline void writeInt(int v) {
    char t[12]; int n = 0;
    if (v == 0) t[n++] = '0';
    while (v) { t[n++] = char('0' + v % 10); v /= 10; }
    while (n) *op++ = t[--n];
}

int main() {
    int len = (int)fread(s_, 1, sizeof(s_) - 1, stdin);
    while (len > 0 && (s_[len - 1] == '\n' || s_[len - 1] == '\r' || s_[len - 1] == ' ')) len--;
    int n = len;
    static int s[MAXN];
    for (int i = 0; i < n; i++) s[i] = s_[i] - 'a' + 1;
    s[n] = 0;
    sa_is(s, 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;
    for (int i = 0; i < n; i++) {
        if (rnk[i] == n - 1) { k = 0; continue; }
        int j = sa_[rnk[i] + 1];
        while (i + k < n && j + k < n && s_[i + k] == s_[j + k]) k++;
        lcp[rnk[i] + 1] = k;
        if (k) k--;
    }
    for (int i = 0; i < n; i++) { if (i) *op++ = ' '; writeInt(sa_[i] + 1); }
    *op++ = '\n';
    for (int i = 1; i < n; i++) { if (i > 1) *op++ = ' '; writeInt(lcp[i]); }
    *op++ = '\n';
    fwrite(outbuf, 1, op - outbuf, stdout);
    return 0;
}

评测结果