代码

#ifndef DUCK_FASTIO_H
#define DUCK_FASTIO_H

typedef unsigned long duck_u64;
typedef long duck_i64;

typedef struct {
    duck_u64 abi_version;
    const char *stdin_ptr;
    duck_u64 stdin_size;
    char *stdout_ptr;
    duck_u64 stdout_limit;
    duck_u64 stdout_size;
    char *stderr_ptr;
    duck_u64 stderr_limit;
    duck_u64 stderr_size;
    const char *ib_ptr;
    duck_u64 ib_limit;
    char *ob_ptr;
    duck_u64 ob_limit;
    duck_u64 tsc_frequency;
} __attribute__((packed)) DuckInfo;

static __attribute__((always_inline)) inline DuckInfo *duck_info(long argc, char **argv) {
    char **p = argv + argc + 1;
    while (*p) ++p;
    duck_u64 *aux = (duck_u64 *)(p + 1);
    while (aux[0]) {
        if (aux[0] == 0x6b637564UL) return (DuckInfo *)aux[1];
        aux += 2;
    }
    return (DuckInfo *)0;
}

static __attribute__((always_inline)) inline duck_u64 duck_read_u64(const char **cursor) {
    const char *p = *cursor;
    while ((unsigned char)(*p - '0') > 9) ++p;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return value;
}

static __attribute__((always_inline)) inline duck_i64 duck_read_i64(const char **cursor) {
    const char *p = *cursor;
    while (*p != '-' && (unsigned char)(*p - '0') > 9) ++p;
    int negative = *p == '-';
    p += negative;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return negative ? -(duck_i64)value : (duck_i64)value;
}

static __attribute__((always_inline)) inline char *duck_write_u64(char *out, duck_u64 value) {
    char tmp[24];
    unsigned n = 0;
    do {
        tmp[n++] = (char)('0' + value % 10);
        value /= 10;
    } while (value);
    do *out++ = tmp[--n]; while (n);
    return out;
}

static __attribute__((always_inline)) inline char *duck_write_i64(char *out, duck_i64 value) {
    if (value < 0) {
        *out++ = '-';
        return duck_write_u64(out, (duck_u64)(-value));
    }
    return duck_write_u64(out, (duck_u64)value);
}

static __attribute__((always_inline, noreturn)) inline void duck_exit(void) {
    __asm__ volatile("mov $60,%%eax;xor %%edi,%%edi;syscall" ::: "rax", "rdi", "rcx", "r11", "memory");
    __builtin_unreachable();
}

#endif


typedef unsigned int u32;

enum { MAXN = 100005, POOL = MAXN * 2 + 64 };

static int text[MAXN], suffix[MAXN], rank_pos[MAXN], lcp[MAXN];
static unsigned char type_pool[POOL];
static int bucket_pool[POOL], map_pool[POOL];
static int lms_pool[POOL], reduced_pool[POOL], rsa_pool[POOL];

static __attribute__((always_inline)) inline int
is_lms(const unsigned char *type, int i) {
    return i > 0 && type[i] && !type[i - 1];
}

static void make_buckets(const int *s, int n, int upper, int *bucket,
                         int ends) {
    for (int i = 0; i <= upper; ++i) bucket[i] = 0;
    for (int i = 0; i < n; ++i) ++bucket[s[i]];
    int sum = 0;
    if (ends) {
        for (int i = 0; i <= upper; ++i) {
            sum += bucket[i];
            bucket[i] = sum;
        }
    } else {
        for (int i = 0; i <= upper; ++i) {
            int count = bucket[i];
            bucket[i] = sum;
            sum += count;
        }
    }
}

static void induce(const int *s, int *sa, int n, int upper,
                   const unsigned char *type, const int *ordered_lms,
                   int m, int *bucket) {
    for (int i = 0; i < n; ++i) sa[i] = -1;
    make_buckets(s, n, upper, bucket, 1);
    for (int i = m; i--;) {
        int p = ordered_lms[i];
        sa[--bucket[s[p]]] = p;
    }

    make_buckets(s, n, upper, bucket, 0);
    for (int i = 0; i < n; ++i) {
        int p = sa[i] - 1;
        if (p >= 0 && !type[p]) sa[bucket[s[p]]++] = p;
    }

    make_buckets(s, n, upper, bucket, 1);
    for (int i = n; i--;) {
        int p = sa[i] - 1;
        if (p >= 0 && type[p]) sa[--bucket[s[p]]] = p;
    }
}

/* s[n-1] must be its unique zero sentinel; all preceding symbols are > 0. */
static void sais(const int *s, int *sa, int n, int upper, int off) {
    if (n == 1) {
        sa[0] = 0;
        return;
    }

    unsigned char *type = type_pool + off;
    int *bucket = bucket_pool + off;
    int *map = map_pool + off;
    int *lms = lms_pool + off;
    int *red = reduced_pool + off;
    int *rsa = rsa_pool + off;

    type[n - 1] = 1;
    for (int i = n - 1; i--;) {
        type[i] = (unsigned char)(s[i] < s[i + 1] ||
                                  (s[i] == s[i + 1] && type[i + 1]));
    }

    int m = 0;
    for (int i = 1; i < n; ++i)
        if (is_lms(type, i)) {
            map[i] = m;
            lms[m++] = i;
        }

    induce(s, sa, n, upper, type, lms, m, bucket);

    int sorted_m = 0;
    for (int i = 0; i < n; ++i)
        if (is_lms(type, sa[i])) rsa[sorted_m++] = sa[i];

    int names = 0;
    int previous = -1;
    for (int i = 0; i < m; ++i) {
        int p = rsa[i];
        int different = previous < 0;
        if (!different) {
            for (int d = 0;; ++d) {
                if (s[p + d] != s[previous + d] ||
                    type[p + d] != type[previous + d]) {
                    different = 1;
                    break;
                }
                int a = is_lms(type, p + d);
                int b = is_lms(type, previous + d);
                if (d && (a || b)) {
                    if (!(a && b)) different = 1;
                    break;
                }
            }
        }
        if (different) ++names;
        red[map[p]] = names - 1;
        previous = p;
    }

    if (names == m) {
        for (int i = 0; i < m; ++i) rsa[red[i]] = i;
    } else {
        sais(red, rsa, m, names - 1, off + n);
    }

    /* rsa now indexes LMS positions in their original text order. */
    for (int i = 0; i < m; ++i) map[i] = lms[rsa[i]];
    induce(s, sa, n, upper, type, map, m, bucket);
}

static __attribute__((always_inline)) inline char *write_u32(char *p, u32 x) {
    char b[10];
    unsigned n = 0;
    do {
        b[n++] = (char)('0' + x % 10u);
        x /= 10u;
    } while (x);
    do *p++ = b[--n]; while (n);
    return p;
}

static void run(DuckInfo *info) {
    const unsigned char *s = (const unsigned char *)info->stdin_ptr;
    int n = 0;
    while ((unsigned)(s[n] - 'a') < 26u) {
        text[n] = (int)(s[n] - 'a') + 1;
        ++n;
    }
    text[n] = 0;
    sais(text, suffix, n + 1, 26, 0);
    for (int i = 0; i < n; ++i) suffix[i] = suffix[i + 1];

    for (int i = 0; i < n; ++i) rank_pos[suffix[i]] = i;
    int h = 0;
    for (int i = 0; i < n; ++i) {
        int r = rank_pos[i];
        if (r == n - 1) {
            h = 0;
            continue;
        }
        int j = suffix[r + 1];
        while (i + h < n && j + h < n && s[i + h] == s[j + h]) ++h;
        lcp[r] = h;
        if (h) --h;
    }

    char *out = info->stdout_ptr;
    for (int i = 0; i < n; ++i) {
        out = write_u32(out, (u32)suffix[i] + 1u);
        *out++ = i + 1 == n ? '\n' : ' ';
    }
    for (int i = 0; i + 1 < n; ++i) {
        out = write_u32(out, (u32)lcp[i]);
        *out++ = i + 2 == n ? '\n' : ' ';
    }
    if (n == 1) *out++ = '\n';
    info->stdout_size = (duck_u64)(out - info->stdout_ptr);
}

#ifndef LOCAL
__attribute__((noreturn))
void __libc_start_main(void *unused, long argc, char **argv) {
    (void)unused;
    DuckInfo *info = duck_info(argc, argv);
    run(info);
    duck_exit();
}
int main(void) {}
#else
extern long read(int, void *, unsigned long);
extern long write(int, const void *, unsigned long);
static char local_in[MAXN], local_out[2000020];
int main(void) {
    long n = read(0, local_in, sizeof(local_in));
    DuckInfo info = {0};
    info.stdin_ptr = local_in;
    info.stdin_size = (duck_u64)n;
    info.stdout_ptr = local_out;
    info.stdout_limit = sizeof(local_out);
    run(&info);
    write(1, local_out, info.stdout_size);
    return 0;
}
#endif

评测结果