设为首页 加入收藏

TOP

loj#6031. 「雅礼集训 2017 Day1」字符串(SAM 广义SAM 数据分治)(一)
2019-03-14 18:08:08 】 浏览:88
Tags:loj#6031. 集训 2017 Day1 字符串 SAM 广义 数据分治

题意

链接

Sol

\(10^5\)次询问每次询问\(10^5\)个区间。。这种题第一感觉就是根号/数据分治的模型。

\(K\)是个定制这个很关键。

考虑\(K\)比较小的情况,可以直接暴力建SAM,\(n^2\)枚举\(w\)的子串算出现次数。询问用个\(n^2\)的vector记录一下每次在vector里二分就好。

\(K\)比较大的情况我没想到什么好的做法,网上的做法复杂度也不是很好。。

然后写了个广义SAM + 暴力跳parent就过了。。

不过这题思想还是很好的

#include<bits/stdc++.h> 
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
#define LL long long 
#define ull unsigned long long 
#define Fin(x) {freopen(#x".in","r",stdin);}
#define Fout(x) {freopen(#x".out","w",stdout);}
using namespace std;
const int MAXN = 4e5 + 10, INF = 1e9 + 1, mod = 1e9 + 7;
const double eps = 1e-9, pi = acos(-1);
template <typename A, typename B> inline bool chmin(A &a, B b){if(a > b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline bool chmax(A &a, B b){if(a < b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline LL add(A x, B y) {if(x + y < 0) return x + y + mod; return x + y >= mod ? x + y - mod : x + y;}
template <typename A, typename B> inline void add2(A &x, B y) {if(x + y < 0) x = x + y + mod; else x = (x + y >= mod ? x + y - mod : x + y);}
template <typename A, typename B> inline LL mul(A x, B y) {return 1ll * x * y % mod;}
template <typename A, typename B> inline void mul2(A &x, B y) {x =
		    

(1ll * x * y % mod + mod) % mod;} 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, Q, K; char s[MAXN], w[MAXN]; string q[MAXN]; int l[MAXN], r[MAXN], a[MAXN], b[MAXN], pos[MAXN]; vector<int> line[1001][1001], v[MAXN]; int ch[MAXN][26], siz[MAXN], len[MAXN], fa[MAXN], las = 1, root = 1, tot = 1; void insert(int x, int opt) { int now = ++tot, pre = las; las = now; len[now] = len[pre] + 1; siz[now] = opt; for(; pre && !ch[pre][x]; pre = fa[pre]) ch[pre][x] = now; if(!pre) fa[now] = root; else { int q = ch[pre][x]; if(len[pre] + 1 == len[q]) fa[now] = q; else { int nq = ++tot; len[nq] = len[pre] + 1; fa[nq] = fa[q]; memcpy(ch[nq], ch[q], sizeof(ch[q])); fa[now] = fa[q] = nq; for(; pre && ch[pre][x] == q; pre = fa[pre]) ch[pre][x] = nq; } } } void dfs(int x) { for(auto &to : v[x]) { dfs(to); siz[x] += siz[to]; } } int Query(vector<int> &q, int a, int b) { return (upper_bound(q.begin(), q.end(), b) - lower_bound(q.begin(), q.end(), a)); } LL solve1(int a, int b) { LL ret = 0; for(int i = 1; i <= K; i++) { int now = root; for(int j = i; j <= K; j++) { int x = w[j] - 'a'; now = ch[now][x]; if(!now) break; else ret += 1ll * siz[now] * Query(line[i][j], a, b); } } return ret; } void Build() { for(int i = 1; i <= tot; i++) v[fa[i]].push_back(i); dfs(root); } signed main() { // freopen("string9.in", "r", stdin); freopen("b.out", "w", stdout); N = read(); M = read(); Q = read(); K = read(); scanf("%s", s + 1); for(int i = 1; i <= N; i++) insert(s[i] - 'a', 1); if(K <= 1000) { Build(); for(int i = 1; i <= M; i++) l[i] = read() + 1, r[i] = read() + 1, line[l[i]][r[i]].push_back(i); for(int i = 1; i <= Q; i++) { scanf("%s", w + 1); int a = read() + 1, b = read() + 1; cout << solve1(a, b) << '\n'; } } else { for(int i = 1; i <= M; i++) l[i] = read() + 1, r[i] = read() + 1; for(int i = 1; i <= Q; i++) { cin >> q[i]; a[i] = r
编程开发网
首页 上一页 1 2 下一页 尾页 1/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇C++_自引用指针this 下一篇Ubuntu下VsCode+CMake 交叉编译

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(217) }