mayoko’s diary

プロコンとかいろいろ。

POJ 3581: Sequence

suffix array まわりの問題をあんまり解いたことがないので解いてみました。蟻本のやつです。

解法

蟻本 338 ページに書いてある通りです。

最初の区切りは「一番大きい数が一番前にある」という制約から, 数列を逆順に見た時の接尾辞で辞書順最小のものを選べば良いことがわかります。これはよくある suffix array ですね(ただし, 「各部分は空であってはいけない」という制約から, 最初に区切るべき位置 p1 は, N-p1 >= 2 を満たさなければならないことに注意)。

残りの部分を 2 つに分けたいです。別れた時の各数列が p, q で, p を逆から見た数列が rp, q を逆から見た数列が rq であるとすると, rp + rq を最小にしたいです。これを逆から見ると q+p になるわけですが, この数列は, p+q を 2 つ並べた数列 p+q+p+q の真ん中の部分と一致します。

よって, p+q を 2 つ並べた数列を逆順にして, その接尾辞で辞書順最小のものを取ってくれば良いです。
注意なのは, p, q はともに空であってはいけないので, 接尾辞の候補はある程度絞られることです。p+q の長さを m として, 分割する場所 p2 は, 1 <= p2 <= m-1 を満たさなければダメです。

あと「rp+rq の後見える数列は考慮しなくて良いのか」と思われるかもしれませんが, それは条件を満たす p2 については全部同じように数列がくっついてるので問題ないです。

const int MAXN = 200010;
namespace SA {
    int rank[2*MAXN], tmp[2*MAXN];
    int n, k;
    bool compare_sa(int i, int j) {
        if (rank[i] != rank[j]) return rank[i] < rank[j];
        int ri = (i+k <= n) ? rank[i+k] : -1;
        int rj = (j+k <= n) ? rank[j+k] : -1;
        return ri < rj;
    }
    // suffix array を構築する
    // O(N log^2 N)
    // how to use: construct_saを呼ぶとsa配列にSuffixArrayを構築する
    void createSA(const int* s, int N, int* sa) {
        n = N;
        // 最初は 1 文字ソート
        for (int i = 0; i <= n; i++) {
            sa[i] = i;
            rank[i] = i < n ? s[i] : -1;
        }
        for (k = 1; k <= n; k*=2) {
            sort(sa, sa+n+1, compare_sa);
            tmp[sa[0]] = 0;
            for (int i = 1; i <= n; i++) {
                tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(sa[i-1], sa[i]) ? 1 : 0);
            }
            for (int i = 0; i <= n; i++) rank[i] = tmp[i];
        }
    }
} // namespace SA

int N, A[MAXN], rev[2*MAXN], sa[2*MAXN];

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) scanf("%d", A+i);
    reverse_copy(A, A+N, rev);
    SA::createSA(rev, N, sa);
    int p1, p2;
    for (int i = 0; i <= N; i++) {
        p1 = N-sa[i];
        if (p1 > 0 && N-p1 >= 2) break;
    }
    int m = N-p1;
    reverse_copy(A+p1, A+N, rev);
    reverse_copy(A+p1, A+N, rev+m);
    SA::createSA(rev, 2*m, sa);
    for (int i = 0; i <= 2*m; i++) {
        p2 = m-sa[i];
        if (p2 > 0 && m-p2 >= 1) break;
    }
    for (int i = p1-1; i >= 0; i--) {
        printf("%d\n", A[i]);
    }
    for (int i = p1+p2-1; i >= p1; i--) {
        printf("%d\n", A[i]);
    }
    for (int i = N-1; i >= p1+p2; i--) {
        printf("%d\n", A[i]);
    }
    return 0;
}