TIOJ 1497：喝醉的宿主 The drunk host

TIOJ 1497：喝醉的宿主 The drunk host

題目大意：給你一個字串 $s$，請你將這個字串的 $n$ 個後綴進行排序，輸出 $n$ 行，第 $i$ 行代表第 $i$ 小後綴的起始位置。

解法：如果直接排序的話要 $O(n^2\times\log(n))$，我們可以使用倍增法的概念，先把字串想成是環狀的，每次先排序好 $s[i, i + 2^k - 1]$，然後就可以利用 $(s[i, i + 2^k - 1], s[i + 2^k, i + 2^{k+1} - 1])$ 排序好 $s[i, i + 2^{k+1} - 1]$，因為是環狀的，所以我們在字串後面加一個最小的字元就能確保它跟用後綴排序的效果是一樣的。如果直接這樣子，那複雜度就是 $O(n\times\log^2(n))$，因為要倍增加上 $\text{sort}$，但是其實可以 $O(n)\ \text{sort}$，我們現在要排序一個二維的東西，那其實可以對第二維排序後再對第一維排序，這叫 $\text{radix sort}$，然後我們現在把要排序的東西改成 $(s[i - 2^k, i - 1], s[i, i + 2^k - 1])$，就可以發現第二維已經在上一次排好了，這次排第一維就好了。需要用到的陣列有 $sa, rnk, cnt, lp, tmp$，分別代表第 $i$ 小後綴的位置、位置 $i$ 的排名、排名出現的次數、$sa_i - 2^k$ 與新的排名。然後要注意這題需要用 $\text{getline}$ 讀入字串。

$\text{Code：}$

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define TIOJQQ ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

vector<int> SA (string s) {
    int n = s.size();
    if (n == 1) return {1};
    s = s + string (1, 0);

    vector<int> sa (n + 1), rnk (n + 1), cnt (n + 1);
    // sa[i] : ith smallest suffix's position
    // rnk[i] : position i's rank

    int al[256] = {};
    FOR (i, 0, n) al[s[i]]++;
    FOR (i, 1, 255) al[i] += al[i - 1];
    FOR (i, 0, n) sa[--al[s[i]]] = i;
    for (int i = 1, now = 0; i <= n; i++) {
        if (s[sa[i]] != s[sa[i - 1]]) now++;
        rnk[sa[i]] = now;
    }

    for (int len = 1; len <= n; len <<= 1) {
        vector<int> lp (n + 1), tmp (n + 1);
        // lp[i] : sa[i] - len
        // tmp[i] : new rank
        fill (cnt.begin(), cnt.end(), 0);
        FOR (i, 0, n) {
            lp[i] = sa[i] - len;
            lp[i] += lp[i] < 0 ? n + 1 : 0;
            cnt[rnk[i]]++;
        }
        FOR (i, 1, n) cnt[i] += cnt[i - 1];
        for (int i = n; i >= 0; i--) sa[--cnt[rnk[lp[i]]]] = lp[i];
        tmp[sa[0]] = 0;
        for (int i = 1, now = 0; i <= n; i++) {
            int np1 = sa[i] + len, np2 = sa[i - 1] + len;
            np1 -= np1 > n + 1 ? n + 1 : 0;
            np2 -= np2 > n + 1 ? n + 1 : 0;
            if (rnk[sa[i]] != rnk[sa[i - 1]] || rnk[np1] != rnk[np2]) now++;
            tmp[sa[i]] = now;
        }
        rnk = tmp;
    }
    sa.erase (sa.begin());
    return sa;
}

void solve() {
    string s;
    getline (cin, s);
    vector<int> v = SA (s);
    for (int x : v) cout << x << '\n';
}

int main() {
    TIOJQQ;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！