@bzoj - 3881@ [Coci2015]Divljak

柔情只为你懂 2023-06-01 12:58 21阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

Alice有n个字符串S\_1,S\_2...S\_n，Bob有一个字符串集合T，一开始集合是空的。  
接下来会发生q个操作，操作有两种形式：  
“1 P”，Bob往自己的集合里添加了一个字符串P。  
“2 x”，Alice询问Bob，集合T中有多少个字符串包含串S\_x。（我们称串A包含串B，当且仅当B是A的子串）  
Bob遇到了困难，需要你的帮助。

**Input**  
第1行，一个数n；接下来n行，每行一个字符串表示S\_i；  
下一行，一个数q；接下来q行，每行一个操作，格式见题目描述。

**Output**  
对于每一个Alice的询问，帮Bob输出答案。

**Sample Input**  
3  
a  
bc  
abc  
5  
1 abca  
2 1  
1 bca  
2 2  
2 3  
**Sample Output**  
1  
2  
1

**HINT**  
1 <= n,q <= 100000；  
Alice和Bob拥有的字符串长度之和各自都不会超过 2000000；  
字符串都由小写英文字母组成。

## @solution@ ##

如果考虑将 T 用个什么东西维护起来，然后把 S 拿上去跑，无论在线还是离线都没什么办法快速维护。

我们考虑对所有 S 串建 AC 自动机，然后把 T 拿上去跑。  
因为 T 的每一个前缀的后缀都是 T 的子串，而 AC 自动机中的 fail 对应的正是该节点的最长可能匹配的后缀。  
我们不妨把 T 的每一个前缀对应的点 x 在 fail 树上做个 x 到 root 的整体链 + 1，就可以快速地将 T 的每个子串更新。

然而。。。这样看似很棒，但其实有一点小小的问题：假如某个子串在 T 中出现了多次，那么上面那个维护方法也会累加多次。  
但是我们只需要一次：即表示这个串是 T 的子串，而不是表示这个串在 T 出现了多少次。  
我们可以将所有链取并集，做一个“链并加”，这样就可以达到我们的目的了。

具体到实现，我们可以类比虚树，将所有点按照 dfs 访问的时间排序。然后在每个点到根的链 + 1 后，将排序后相邻两个点的 lca 到根的链 - 1。  
链加与单点查询可以简单地转为单点加与子树查询，这样就可以 dfs 序上树状数组维护。

时间复杂度 O(nlogn)。

## @accepted code@ ##

#include<queue> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAXN = 100000; const int MAXS = 2000000; struct BIT{ int tree[MAXS + 5], tot; int lowbit(int x) {return x & (-x);} void update(int x, int k) { for(int i=x;i<=tot;i+=lowbit(i)) tree[i] += k; // printf(". %d %d\n", x, k); } int sum(int x) { int ret = 0; for(int i=x;i;i-=lowbit(i)) ret += tree[i]; return ret; } }T; struct Graph{ struct edge{ edge *nxt; int to; }edges[MAXS + 5], *adj[MAXS + 5], *ecnt; Graph() {ecnt = &edges[0];} void addedge(int u, int v) { edge *p = (++ecnt); p->to = v, p->nxt = adj[u], adj[u] = p; // printf("! %d %d\n", u, v); } int siz[MAXS + 5], dep[MAXS + 5], hvy[MAXS + 5], fa[MAXS + 5]; void dfs1(int x, int f) { siz[x] = 1; fa[x] = f; dep[x] = dep[f] + 1; hvy[x] = 0; for(edge *p=adj[x];p;p=p->nxt) { if( p->to == f ) continue; dfs1(p->to, x); siz[x] += siz[p->to]; if( siz[p->to] > siz[hvy[x]] ) hvy[x] = p->to; } } int tid[MAXS + 5], dfn[MAXS + 5], top[MAXS + 5], dcnt; void dfs2(int x, int tp) { top[x] = tp; dfn[++dcnt] = x; tid[x] = dcnt; if( hvy[x] ) dfs2(hvy[x], tp); for(edge *p=adj[x];p;p=p->nxt) { if( p->to == fa[x] || p->to == hvy[x] ) continue; dfs2(p->to, p->to); } } void build() {dfs1(1, 0); dfs2(1, 1); T.tot = dcnt;} int lca(int u, int v) { while( top[u] != top[v] ) { if( dep[top[u]] < dep[top[v]] ) swap(u, v); u = fa[top[u]]; } if( dep[u] < dep[v] ) swap(u, v); return v; } }G; bool cmp(int x, int y) {return G.tid[x] < G.tid[y];} struct ACM{ struct node{int ch[26], fail;}nd[MAXS + 5]; int root, ncnt; ACM() {root = ncnt = 0;} int add_string(char *S) { int lenS = strlen(S), nw = root; for(int i=0;i<lenS;i++) { if( !nd[nw].ch[S[i] - 'a'] ) nd[nw].ch[S[i] - 'a'] = (++ncnt); nw = nd[nw].ch[S[i] - 'a']; } return nw + 1; } void link(int a, int b) { nd[b].fail = a, G.addedge(a + 1, b + 1); } int arr[MAXS + 5]; void build() { int hd = 1, tl = 0; for(int i=0;i<26;i++) if( nd[root].ch[i] ) { arr[++tl] = nd[root].ch[i]; link(root, nd[root].ch[i]); } else nd[root].ch[i] = root; while( hd <= tl ) { int f = arr[hd++]; for(int i=0;i<26;i++) { if( !nd[f].ch[i] ) nd[f].ch[i] = nd[nd[f].fail].ch[i]; else { arr[++tl] = nd[f].ch[i]; link(nd[nd[f].fail].ch[i], nd[f].ch[i]); } } } } void modify(char *S) { int rt = root; int lenS = strlen(S); for(int i=0;i<lenS;i++) { rt = nd[rt].ch[S[i] - 'a']; arr[i] = rt + 1; // printf("? %d %d\n", arr[i], rt - pl + 1); } sort(arr, arr + lenS, cmp); for(int i=0;i<lenS;i++) T.update(G.tid[arr[i]], 1); for(int i=1;i<lenS;i++) T.update(G.tid[G.lca(arr[i-1], arr[i])], -1); } }ac; char S[MAXS + 5]; int id[MAXN + 5]; int main() { int n, q; scanf("%d", &n); for(int i=1;i<=n;i++) { scanf("%s", S); id[i] = ac.add_string(S); } ac.build(), G.build(); scanf("%d", &q); for(int i=1;i<=q;i++) { int op; scanf("%d", &op); if( op == 1 ) { scanf("%s", S); ac.modify(S); } else { int x; scanf("%d", &x); printf("%d\n", T.sum(G.tid[id[x]] + G.siz[id[x]] - 1) - T.sum(G.tid[id[x]] - 1)); } } }

## @details@ ##

这道题。。。它卡我倍增的 lca 的空间。。。我写了树链剖分求 lca 才过的。。。

顺便这道题也可以用 sam 建，不过就有些大材小用之感。。。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11362000.html