「BZOJ 1692」队列变换 - 后缀数组 + 贪心

对于一个字符串 ，每次从它的首部或尾部弹出一个字符，加入到 的尾部，求可以构造出的字典序最小的 。

链接

BZOJ 1692

题解

贪心，如果没有重复字符，则每次从两边选一个字典序较小的字符即可。

因为有重复字符，所以可以继续比较，直到找到某一边一个字典序较小的字符即可，这个过程使用后缀数组优化。

注意输出 80 个字符后换行。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

const int MAXN = 30000 * 2 + 1;

int n, sa[MAXN], rk[MAXN];
char s[MAXN];

inline void suffixArray() {
    static int set[MAXN], a[MAXN];
    std::copy(s, s + n, set);
    std::sort(set, set + n);
    int *end = std::unique(set, set + n);
    for (int i = 0; i < n; i++) a[i] = std::lower_bound(set, end, s[i]) - set;

    static int fir[MAXN], sec[MAXN], tmp[MAXN], _buc[MAXN + 1], *buc = _buc + 1;
    for (int i = 0; i < n; i++) buc[a[i]]++;
    for (int i = 0; i < n; i++) buc[i] += buc[i - 1];
    for (int i = 0; i < n; i++) rk[i] = buc[a[i] - 1];

    for (int t = 1; t < n; t *= 2) {
        for (int i = 0; i < n; i++) fir[i] = rk[i], sec[i] = i + t < n ? rk[i + t] : -1;

        std::fill(buc - 1, buc + n, 0);
        for (int i = 0; i < n; i++) buc[sec[i]]++;
        for (int i = 0; i < n; i++) buc[i] += buc[i - 1];
        for (int i = 0; i < n; i++) tmp[n - buc[sec[i]]--] = i;

        std::fill(buc - 1, buc + n, 0);
        for (int i = 0; i < n; i++) buc[fir[i]]++;
        for (int i = 0; i < n; i++) buc[i] += buc[i - 1];
        for (int i = 0; i < n; i++) sa[--buc[fir[tmp[i]]]] = tmp[i];

        for (int i = 0; i < n; i++) {
            if (!i) rk[sa[i]] = 0;
            else if (fir[sa[i]] == fir[sa[i - 1]] && sec[sa[i]] == sec[sa[i - 1]]) rk[sa[i]] = rk[sa[i - 1]];
            else rk[sa[i]] = rk[sa[i - 1]] + 1;
        }
    }

    // for (int i = 0; i < n; i++) printf("%d%c", sa[i], i == n - 1 ? '\n' : ' ');
    // for (int i = 0; i < n; i++) printf("%d%c", rk[i], i == n - 1 ? '\n' : ' ');
    // for (int i = 0; i < n; i++) printf("%s\n", &s[sa[i]]);
}


int main() {
    // scanf("%s", s);
    // n = strlen(s);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", &s[i]);
    }
    std::copy(s, s + n, s + n + 1);
    std::reverse(s + n + 1, s + n + 1 + n);
    s[n] = '
;
    n = n * 2 + 1;
    s[n] = '\0';

    suffixArray();

    n /= 2;
    for (int i = 0, l = 0, r = 0; i < n; i++) {
        if (l < n && rk[l] < rk[n + 1 + r]) putchar(s[l++]);
        else putchar(s[n - 1 - r++]);
        if ((i + 1) % 80 == 0) putchar('\n');
    }
    // putchar('\n');

    return 0;
}