BZOJ4556: [Tjoi2016&Heoi2016]字符串

命題

有一个长为$n$的字符串$s$和$m$个詢問,每个詢問均有$a,b,c,d$四个参数,问子串$s[a\dots b]$的所有子串和$s[c\dots d]$的最长公
共前缀的长度的最大值是多少。


最長公共前綴暗示著應使用後綴數組,處理好相應的數組后暴力使用ST表匹配的複雜度為$O(n^2)$,無法解決問題。

這個問題最棘手的地方是存在的限制過多:因為是處理所有子串,即使使用後綴數組求出了$LCP$(最長公共前綴),還需要受多個字符串長度的限制才能得到最終答案。

所以不妨考慮先確定一個答案的長度來簡化問題,設該答案為$x$,則僅有$[a,b-x+1]$為可行的左端點。我們假設$x$是答案,把以$c$為左端點的後綴的排名分別向前、向後拓展,找到最長的一個區間$[l,r]$使得它們的$LCP\geq x$,這時如果$[a,b-x+1]$中的存在一個端點的後綴的排名出現在$[l,r]$之間,則可以確定真正的答案至少為$x$。

這時我們發現小於$x$的一定成立,大於$x$的在某一個值后就永遠不成立,由此可知答案具有單調性,所以直接二分答案。

可如何確定是否$[a,b-x+1]$中的存在一個端點的後綴的排名出現在$[l,r]$之間呢?對於區間我們需要一棵線段樹來維護在某一“時刻”原字符串的某一後綴是否出現,所以把後綴數組的各個元素看做時間軸,每一個時刻按後綴數組的次序添加相應後綴,可使用主席樹進行可持久化。

時間複雜度為$O(mlog^2n)$,空間複雜度為$O(nlogn)$。

一開始寫的程序TLE,十分不解,去LibreOJ下載數據測了一遍發現后幾個點跑3秒+,更加十分不解。偶然看到有人預處理了ST表查詢中$log$的答案,於是乎也改成了預處理,然後。。。奇跡發生了。

所以在此強烈聲明:複雜度集中的地方切記不要使用內置函數,請盡量自行實現或直接預處理

($pow$,$log2$哭暈在廁所。。。)

#include <algorithm> #include <cstring> #include <cstdio> #include <cctype> #include <cmath> template <typename _Tp> void read(_Tp &a, char c = 0) { for (c = getchar(); !isdigit(c); c = getchar()); for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar()); } const int N = 1e5 + 5; const int k = 21; int n, m, sa[N], rk[N], ht[N]; char r[N]; namespace SPARSE_TABLE { int st[N][21], Log[N]; void getST(int n, int *ht) { for (int i = 2; i <= n; i++) Log[i] = Log[i >> 1] + 1; memset(st, 127 / 3, sizeof st); for (int i = 1; i <= n; i++) st[i][0] = ht[i]; for (int j = 1; j < 21; j++) for (int i = 1; i + (1 << (j - 1)) <= n; i++) st[i][j] = std :: min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]); } int getMin(int l, int r) { int k = Log[r - l + 1]; return std :: min(st[l][k], st[r - (1 << k) + 1][k]); } } namespace SUFFIX_ARRAY { int buf1[N], buf2[N], buc[N]; void sort(char *s, int n, int *sa, int *rk, int *ht) { int *x = buf1, *y = buf2, m = 26; for (int i = 0; i <= m; i++) buc[i] = 0; for (int i = 1; i <= n; i++) buc[x[i] = s[i] - 'a' + 1]++; for (int i = 1; i <= m; i++) buc[i] += buc[i - 1]; for (int i = n; i; i--) sa[buc[x[i]]--] = i; for (int k = 1; k <= n; k <<= 1) { int p = 0; for (int i = n - k + 1; i <= n; i++) y[++p] = i; for (int i = 1; i <= n; i++) if (sa[i] > k) y[++p] = sa[i] - k; for (int i = 0; i <= m; i++) buc[i] = 0; for (int i = 1; i <= n; i++) buc[x[y[i]]]++; for (int i = 1; i <= m; i++) buc[i] += buc[i - 1]; for (int i = n; i; i--) sa[buc[x[y[i]]]--] = y[i]; std :: swap(x, y), x[sa[1]] = p = 1; for (int i = 2; i <= n; i++) if (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k]) x[sa[i]] = p; else x[sa[i]] = ++p; if ((m = p) >= n) break; } for (int i = 1; i <= n; i++) rk[sa[i]] = i; for (int k = 0, j = 0, i = 1; i <= n; ht[rk[i++]] = k) for (k ? k-- : 0, j = sa[rk[i] - 1]; s[i + k] == s[j + k]; k++); } } namespace FUNC_SEGMENT_TREE { int tot, rt[N]; struct node { int l, r, val; } tr[k * N]; void __add(int &x, int y, int l, int r, int p) { x = ++tot; (tr[x] = tr[y]).val++; if (l == r) return; int mid = (l + r) >> 1; if (p <= mid) __add(tr[x].l, tr[y].l, l, mid, p); else __add(tr[x].r, tr[y].r, mid + 1, r, p); } void add(int *sa, int n) { for (int i = 1; i <= n; i++) __add(rt[i], rt[i - 1], 1, n, sa[i]); } int __ask(int x, int l, int r, int L, int R) { if (!x) return 0; if (L <= l && r <= R) return tr[x].val; int ret = 0, mid = (l + r) >> 1; if (L <= mid) ret += __ask(tr[x].l, l, mid, L, R); if (R > mid) ret += __ask(tr[x].r, mid + 1, r, L, R); return ret; } int ask(int l, int r, int a, int b, int n) { return __ask(rt[r], 1, n, a, b) - __ask(rt[l - 1], 1, n, a, b); } } namespace DEFAULT { bool check(int x, int a, int b, int c, int d) { int L, R, l, r, mid = 0; L = rk[c], R = n + 1; while (L + 1 < R) { mid = (L + R) >> 1; SPARSE_TABLE :: getMin(rk[c] + 1, mid) >= x ? L = mid : R = mid; } r = L; L = 0, R = rk[c]; while (L + 1 < R) { mid = (L + R) >> 1; SPARSE_TABLE :: getMin(mid + 1, rk[c]) >= x ? R = mid : L = mid; } l = R; return FUNC_SEGMENT_TREE :: ask(l, r, a, b - x + 1, n); } } int main() { read(n), read(m); scanf("%s", r + 1); SUFFIX_ARRAY :: sort(r, n, sa, rk, ht); SPARSE_TABLE :: getST(n, ht); FUNC_SEGMENT_TREE :: add(sa, n); register int a, b, c, d; while (m--) { read(a), read(b), read(c), read(d); int L = 0, R = std :: min(d - c + 1, b - a + 1) + 1, mid = 0; while (L + 1 < R) { mid = (L + R) >> 1; DEFAULT :: check(mid, a, b, c, d) ? L = mid : R = mid; } printf("%d\n", L); } return 0; }
Code language: PHP (php)

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注