洛谷P3763 [TJOI2017]DNA(后缀数组 RMQ)
程序员文章站
2022-04-09 19:05:51
题意 "题目链接" Sol 这题打死我也不会想到后缀数组的,应该会全程想AC自动机之类的吧 但知道这题能用后缀数组做之后应该就不是那么难了 首先把$S$和$S0$拼到一起跑,求出Height数组 暴力枚举每个后缀是否能成为答案。 具体来说,每次比较当前后缀和$S_0$的lcp,如果长度$ using ......
题意
sol
这题打死我也不会想到后缀数组的,应该会全程想ac自动机之类的吧
但知道这题能用后缀数组做之后应该就不是那么难了
首先把\(s\)和\(s0\)拼到一起跑,求出height数组
暴力枚举每个后缀是否能成为答案。
具体来说,每次比较当前后缀和\(s_0\)的lcp,如果长度\(< n\)的话就从不合法的位置继续匹配
rmq维护一下区间lcp最小值
bzoj上被完美卡常
// luogu-judger-enable-o2 #include<bits/stdc++.h> using namespace std; const int maxn = 2e5 + 10; const int inf = 2333; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, m, l, rak[maxn], tax[maxn], tp[maxn], sa[maxn], h[maxn], f[maxn][20], lg2[maxn]; char s[maxn], s0[maxn]; void qsort() { for(int i = 0; i <= m; i++) tax[i] = 0; for(int i = 1; i <= n; i++) tax[rak[i]]++; for(int i = 1; i <= m; i++) tax[i] += tax[i - 1]; for(int i = n; i >= 1; i--) sa[tax[rak[tp[i]]]--] = tp[i]; } void suffixsort() { for(int i = 1; i <= n; i++) rak[i] = s[i], tp[i] = i; m = 233; qsort(); for(int w = 1, p = 0; p < n; w <<= 1, m = p) { p = 0; for(int i = 1; i <= w; i++) tp[++p] = n - i + 1; for(int i = 1; i <= n; i++) if(sa[i] > w) tp[++p] = sa[i] - w; qsort(); swap(tp, rak); rak[sa[1]] = p = 1; for(int i = 2; i <= n; i++) rak[sa[i]] = (tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w]) ? p : ++p; } for(int i = 1, k = 0; i <= n; i++) { if(k) k--; int j = sa[rak[i] - 1]; while(s[i + k] == s[j + k]) k++; h[rak[i]] = k; } } void pre() { for(int i = 1; i <= n; i++) f[i][0] = h[i]; for(int j = 1; j <= 17; j++) for(int i = 1; i + (1 << j) - 1 <= n; i++) f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]); } int query(int x, int y) { if(x > y) swap(x, y); x++; int k = lg2[y - x + 1]; return min(f[x][k], f[y - (1 << k) + 1][k]); } int check(int x, int y, int dep) { if(dep == 3) return query(rak[x], rak[y]); int num = query(rak[x], rak[y]); num += check(x + num + 1, y + num + 1, dep + 1) + 1; return num; } void solve() { scanf("%s%s", s + 1, s0 + 1); l = strlen(s0 + 1); n = strlen(s + 1); for(int i = 1; i <= l; i++) s[n + i] = s0[i]; n += l; suffixsort(); pre(); n -= l; int ans = 0; for(int i = 1; i <= n - l + 1; i++) if(check(i, n + 1, 0) >= l) ans++; printf("%d\n", ans); } int main() { //freopen("a.in", "r", stdin); lg2[1] = 0; for(int i = 2; i <= maxn - 1; i++) lg2[i] = lg2[i >> 1] + 1; for(int t = read(); t; solve(), t--); return 0; } /* 2 atcgcccta cttca atcgcccta cttca */
上一篇: js 原型,原型链,原型链继承浅析
下一篇: css 选择器基础