POJ 3623 Best Cow Line：後綴數組構造字典序最小字符串

問題描述

給定長度 N (≤ 30,000) 的大寫字母序列，每次只能從左端或右端取一個字符拼接到新序列末尾。求能構造出的字典序最小的新序列。輸出時每行 80 字符。

核心觀察

當左右端字符不同時，直接取較小者；當相同時（如 A...A），需向內比較後續字符，直到出現差異或走到中間。這本質上是在比較兩個後綴的字典序：S[i..j] 與 reverse(S[i..j])。

後綴數組解法

1. 將原串 S 與其逆序串 S' 拼接：T = S + '#' + S'（# 為哨兵，ASCII 小於 A）。
2. 對 T 構建後綴數組 SA 與 Rank 數組。Rank[k] 表示以 k 開頭的後綴在所有後綴中的排名（排名越小字典序越小）。
3. 雙指針 l=0, r=N-1，每次比較 Rank[l] 與 Rank[2N - r]（對應逆序串中位置）：
   • 若 Rank[l] < Rank[2N - r]，取 S[l++]；
   • 否則取 S[r--]。
4. 輸出結果，每 80 字符換行。

關鍵點：Rank 數組的含義

Rank[i] = 以 i 為起始位置的後綴在字典序中的排名。比較 Rank[l] 與 Rank[2N - r] 等價於比較 S[l..] 與 reverse(S[..r]) 的字典序，正是我們需要的決策依據。

複雜度分析

• 構建後綴數組：O(N log N)（倍增算法）或 O(N)（DC3/SA-IS）。
• 構造答案：O(N)。
• 空間：O(N)。

N ≤ 30,000 時，O(N log N) 完全足夠。

參考代碼框架

#include 
using namespace std;
const int MAXN = 60010; // 2*N + 5
int sa[MAXN], rnk[MAXN], tmp[MAXN], h[MAXN];
char s[MAXN], t[MAXN];

bool cmp_sa(int i, int j, int k, int n) {
    if (rnk[i] != rnk[j]) return rnk[i] < rnk[j];
    int ri = i + k <= n ? rnk[i + k] : -1;
    int rj = j + k <= n ? rnk[j + k] : -1;
    return ri < rj;
}

void build_sa(char *str, int n) {
    for (int i = 0; i <= n; i++) {
        sa[i] = i;
        rnk[i] = i < n ? str[i] : -1;
    }
    for (int k = 1; k <= n; k <<= 1) {
        auto cmp = [&](int i, int j) { return cmp_sa(i, j, k, n); };
        sort(sa, sa + n + 1, cmp);
        tmp[sa[0]] = 0;
        for (int i = 1; i <= n; i++)
            tmp[sa[i]] = tmp[sa[i-1]] + cmp(sa[i-1], sa[i]);
        for (int i = 0; i <= n; i++) rnk[i] = tmp[i];
    }
}

int main() {
    int N; scanf("%d", &N);
    for (int i = 0; i < N; i++) scanf(" %c", &s[i]);
    // 構建 T = s + '#' + reverse(s)
    int len = 0;
    for (int i = 0; i < N; i++) t[len++] = s[i];
    t[len++] = '#';
    for (int i = N-1; i >= 0; i--) t[len++] = s[i];
    t[len] = 0;
    build_sa(t, len);
    // 雙指針構造答案
    int l = 0, r = N - 1, cnt = 0;
    while (l <= r) {
        if (rnk[l] < rnk[2*N - r]) putchar(s[l++]);
        else putchar(s[r--]);
        if (++cnt % 80 == 0) putchar('\n');
    }
    if (cnt % 80) putchar('\n');
    return 0;
}

替代方案：直接雙指針模擬

無需後綴數組，直接用兩個指針向內掃描比較，最壞 O(N²) 但平均極快，N=30000 也能通過。代碼更短，適合比賽現場：

while (l <= r) {
    bool left = false;
    for (int i = 0; l + i <= r; i++) {
        if (s[l+i] < s[r-i]) { left = true; break; }
        if (s[l+i] > s[r-i]) { left = false; break; }
    }
    putchar(left ? s[l++] : s[r--]);
}