TIOJ 2155：對發票 again

TIOJ 2155：對發票 again

題目大意：有 $n$ 個字串，請找出一個字串 $s$，使得 $s$ 在這 $n$ 個字串裡都各恰好出現一次。

解法：我們將這 $n$ 個字串用 $n-1$ 個 $\text{\$}$ 接起來，找出 $sa$ 與 $lcp$，接著每 $n$ 個後綴看一次，假設 $n-1$ 個 $lcp$ 裡最小的那個長度是 $len$，且 $len > 0$、$n$ 個 $sa$ 都恰好分別屬於 $n$ 個字串裡的其中一個，並且往前與往後的 $lcp<len$，那這個長度為 $len$ 的字串就是答案，否則如果沒找到就輸出 $7122$。

$\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);
    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);
        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;
}

vector<int> LCP (string s, vector<int> sa) {
    int n = s.size(), len = 0;
    vector<int> rnk (n), lcp (n - 1);
    for (int i = 0; i < n; i++) rnk[sa[i]] = i;
    for (int i = 0; i < n; i++) {
        if (rnk[i] == n - 1) {
            len = 0;
            continue;
        }
        int j = sa[rnk[i] + 1];
        while (i + len < n && j + len < n && s[i + len] == s[j + len]) len++;
        lcp[rnk[i]] = len;
        len = max (0, len - 1);
    }
    return lcp;
}

const int SIZE = 2e5 + 5;

int n;
string s;
vector<int> sa, lcp;
deque<pair<int, int>> st;
int id[2 * SIZE], cnt[SIZE], tot;

void Add (int p) {
    tot += !cnt[id[p]];
    cnt[id[p]]++;
}

void Del (int p) {
    cnt[id[p]]--;
    tot -= !cnt[id[p]];
}

void solve() {
    cin >> n;
    FOR (i, 1, n) {
        string t;
        int start = s.size();
        cin >> t, s += t;
        if (i < n) s += "$";
        for (int j = start; j < s.size(); j++) id[j] = i;
    }
    if (n == 1) {cout << s << '\n'; return;}
    sa = SA (s);
    lcp = LCP (s, sa);
    for (int i = 0; i < n - 1; i++) {
        Add (sa[i]);
        while (st.size() && lcp[i] <= st.back().F) st.pop_back();
        st.pb (lcp[i], i);
    }
    for (int i = n - 1; i < sa.size(); i++) {
        Add (sa[i]);
        int len = st.front().F;
        if (tot == n && len > 0 && (i == n - 1 || lcp[i - n] < len) && (i + 1 == sa.size() || lcp[i] < len)) {
            cout << s.substr (sa[i], len) << '\n';
            return;
        }
        Del (sa[i - n + 1]);
        if (st.front().S == i - n + 1) st.pop_front();
        if (i + 1 < sa.size()) {
            while (st.size() && lcp[i] <= st.back().F) st.pop_back();
            st.pb (lcp[i], i);
        }
    }
    cout << "7122\n";
}

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

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