Luogu P2463 [SDOI2008]Sandy的卡片

題目鏈接 \(Click\) \(Here\)

真的好麻煩啊。。事實證明，理解是理解，一定要認認真真把板子打牢，不然調鍋的時候真的會很痛苦。。（最好是八分鐘能無腦把\(SA\)碼對的程度\(QAQ\)）

這個題最開始我想的是\(RMQ\)遍歷每一個子區間，但是意識到復雜度是\(O(N^2)\)然后就\(GG\)了。怎么說呢，后綴數組和二分似乎是很常見的組合（和莫隊也是？），這個題只需要在\(height\)數組里二分\(lcp\)長度即可，\(check\)函數里面處理一下，要讓區間內所有原串都有至少一個子串。

#include <bits/stdc++.h>
using namespace std;const int N = 200010;int s[N], id[N];
int n, m, num, len, tot = 10000;
int sa[N], tp[N], rk[N], _rk[N], bin[N], height[N];void get_height (int n) {int k = 0;for (int i = 1; i <= n; ++i) {if (k != 0) k--;int j = sa[rk[i] - 1];while (s[i + k] == s[j + k]) k++;height[rk[i]] = k;}
}void base_sort (int n, int m) {for (int i = 0; i <= m; ++i) bin[i] = 0;for (int i = 1; i <= n; ++i) bin[rk[tp[i]]]++;for (int i = 1; i <= m; ++i) bin[i] += bin[i - 1];for (int i = n; i >= 1; --i) sa[bin[rk[tp[i]]]--] = tp[i];
}void suffix_sort (int n, int m) {for (int i = 1; i <= n; ++i) {rk[i] = s[i];tp[i] = i;}base_sort (n, m);for (int w = 1; w <= n; w <<= 1) {int cnt = 0;for (int i = n - w + 1; i <= n; ++i) {tp[++cnt] = i;}for (int i = 1; i <= n; ++i) {if (sa[i] > w) {tp[++cnt] = sa[i] - w;}}base_sort (n, m);memcpy (_rk, rk, sizeof (rk));rk[sa[1]] = cnt = 1;for (int i = 2; i <= n; ++i) {rk[sa[i]] = _rk[sa[i]] == _rk[sa[i - 1]] && _rk[sa[i] + w] == _rk[sa[i - 1] + w] ? cnt : ++cnt;}if (cnt == n) break;m = cnt;}
}bool vis[1010]; int sta[N], top = 0;bool can_use (int l) {while (top) vis[sta[top--]] = false;for (int i = 1; i <= len; ++i) {if (height[i] < l) {while (top) vis[sta[top--]] = false;}if (!vis[id[sa[i]]]) {vis[id[sa[i]]] = true;sta[++top] = id[sa[i]];if (top == n) return true;}}return false;
}int main () {cin >> n;int ban = 2000;for (int i = 1; i <= n; ++i) {cin >> m;for (int j = 1; j <= m; ++j) {cin >> s[++len]; //把所有的字符串整合到一個里id[len] = i; // 表明主權（len號后綴（的lcp）屬于串i）}s[++len] = ++ban; //隔開}for (int i = len; i >= 1; --i) {s[i] = s[i] - s[i - 1] + 4000;}suffix_sort (len, 10000);get_height (len);int l = 0, r = len;while (l < r) {int mid = (l + r + 1) >> 1;if (can_use (mid)) {l = mid;} else {r = mid - 1;}}cout << l + 1 << endl;
}