相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3881
神犇题解:http://trinkle.is-programmer.com/2015/6/30/bzoj-3881.100056.html
解题报告
考虑把Alice的串建成AC自动机
那么每一次用Bob的串去匹配就是Fail树上一些树链的并
这个用BIT+虚树无脑维护一下就可以了
Code
#include<bits/stdc++.h> #define LL long long #define lowbit(x) ((x)&-(x)) using namespace std; const int N = 2000009; const int LOG = 26; const int SGZ = 26; int in[N]; inline int read() { char c = getchar(); int ret = 0, f = 1; for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar()); for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar()); return ret * f; } class Ac_Automaton{ int root, cnt, ch[N][SGZ], fail[N], pos[N], dep[N]; int head[N], to[N], nxt[N], ot[N], fa[N][LOG]; class FenwickTree{ int mx, sum[N]; public: inline void init(int nn) { mx = nn; } inline void modify(int p, int d) { for (int i = p; i <= mx; i += lowbit(i)) { sum[i] += d; } } inline int query(int l, int r) { int ret = 0; for (int i = l - 1; i > 0; i -= lowbit(i)) { ret -= sum[i]; } for (int i = r; i; i -= lowbit(i)) { ret += sum[i]; } return ret; } private: }bit; public: inline void insert(char *s, int nn, int id) { int w = root; for (int i = 1; i <= nn; i++) { int cc = s[i] - 'a'; if (!ch[w][cc]) { ch[w][cc] = ++cnt; } w = ch[w][cc]; } pos[id] = w; } inline void build() { static queue<int> que; for (int i = 0; i < SGZ; i++) { if (ch[root][i]) { que.push(ch[root][i]); } } for (; !que.empty(); que.pop()) { int w = que.front(); AddEdge(fail[w], w); for (int i = 0; i < SGZ; i++) { if (!ch[w][i]) { ch[w][i] = ch[fail[w]][i]; } else { que.push(ch[w][i]); fail[ch[w][i]] = ch[fail[w]][i]; } } } DFS(0, 0); for (int j = 1; j < LOG; j++) { for (int i = 0; i <= cnt; i++) { fa[i][j] = fa[fa[i][j - 1]][j - 1]; } } bit.init(cnt + 1); } inline void match(char *s, int nn) { static vector<int> vt[N]; static int que[N], stk[N], vis[N]; int qtot = 0, stot = 0, vtot = 0; que[++qtot] = root; for (int i = 1, w = root; i <= nn; i++) { w = ch[w][s[i] - 'a']; que[++qtot] = w; } sort(que + 1, que + 1 + qtot); qtot = unique(que + 1, que + 1 + qtot) - que - 1; sort(que + 1, que + 1 + qtot, cmp); for (int i = 1; i <= qtot; i++) { if (stot) { int lca = LCA(que[i], stk[stot]); for (; stot && dep[stk[stot]] > dep[lca]; --stot) { if (stot > 1 && dep[stk[stot - 1]] >= dep[lca]) { vt[stk[stot - 1]].push_back(stk[stot]); } else { vt[lca].push_back(stk[stot]); } } if (stot && stk[stot] != lca) { stk[++stot] = lca; vis[++vtot] = lca; } } stk[++stot] = que[i]; vis[++vtot] = que[i]; } for (; stot > 1; --stot) { vt[stk[stot - 1]].push_back(stk[stot]); } update(root, vt); for (int i = 1; i <= vtot; i++) { vt[vis[i]].clear(); } } inline int query(int id) { return bit.query(in[pos[id]], ot[pos[id]]); } private: inline void update(int w, vector<int> *vt) { for (int i = 0; i < (int)vt[w].size(); i++) { bit.modify(in[w], -1); bit.modify(in[vt[w][i]], 1); update(vt[w][i], vt); } } inline int LCA(int a, int b) { if (dep[a] < dep[b]) { swap(a, b); } for (int j = SGZ - 1; ~j; j--) { if (dep[fa[a][j]] >= dep[b]) { a = fa[a][j]; } } if (a == b) { return a; } for (int j = SGZ - 1; ~j; j--) { if (fa[a][j] != fa[b][j]) { a = fa[a][j]; b = fa[b][j]; } } return fa[a][0]; } static bool cmp(int a, int b) { return in[a] < in[b]; } inline void DFS(int w, int f) { static int tt = 0; in[w] = ++tt; dep[w] = dep[fa[w][0] = f] + 1; for (int i = head[w]; i; i = nxt[i]) { DFS(to[i], w); } ot[w] = tt; } inline void AddEdge(int u, int v) { static int E = 1; to[++E] = v; nxt[E] = head[u]; head[u] = E; } }ac; int main() { static char ss[N]; int n = read(); for (int i = 1; i <= n; i++) { scanf("%s", ss + 1); int len = strlen(ss + 1); ac.insert(ss, len, i); } ac.build(); int m = read(); for (int i = 1; i <= m; i++) { if (read() == 1) { scanf("%s", ss + 1); int len = strlen(ss + 1); ac.match(ss, len); } else { printf("%d\n", ac.query(read())); } } return 0; }