c/c++语言开发共享CF1207G Indie Album

题目链接

problem

有(n)个字符串,对于第(i)个字符串通过以下两种方式中的一个给出。

1. (1; c)，该字符串只含一个字符(c)。

2. (2 x c),该字符串为第(x(1le x < i))个字符串末尾添加一个字符(c)得到。

有(m)次询问，每次询问给出一个字符串(s)和位置编号(x),问在上述第(x)个字符串中，字符串(s)出现了几次。

solution

需要用到(ac)自动机，树状数组，(dfs)序。

首先将询问离线下来，对于所有询问的字符串建立一个(ac)自动机，从而求出(fail)树。然后利用(fail)树的性质:一个字符串在母串中出现的次数为将母串在ac自动机上跑一遍并将走到的位置权值+1，该字符串所对应的(fail)节点的子树权值和。

还有一个需要解决的问题，如果将母串在ac自动机上跑，如果暴力跑显然不行。所以我们发现他给出这(n) 个字符串的方式也是一棵树的形式。所以我们就可以用以下方式跑。

dfs(u,p) {//u为当前节点，p为其父亲在ac自动机上所跑到的节点     将p移向u在ac自动机上跑到的节点     将p所对应的的节点权值+1     for(v是u的儿子) dfs(v,p)     统计所有对于u这个串的查询的答案。     将p所对应的节点权值-1 }

发现通过上面的方式，就可以保证每次查询的时候只有所查询的字符串在(ac)自动机上产生了贡献。

在(fail)树上查询子树权值和,可以用(dfs)序+树状数组完成。

code

//@author: wxyww #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> #include<cmath> #include<map> #include<string> using namespace std; typedef long long ll; const int n =  400010; ll read() {     ll x = 0,f = 1; char c = getchar();     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; } char ss[n],s[n]; int fail[n],trie[n][30]; struct node {     int v,nxt; }e[n]; int idtot,siz[n],tree[n],fa[n],bh[n],ans[n],head[n],ejs,tot; void add(int u,int v) {     e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs; } vector<pair<int,int> >que[n]; void update(int pos,int c) {     while(pos <= idtot) {         tree[pos] += c;         pos += pos & -pos;     } } int query(int pos) {     int ret = 0;     while(pos) {         ret += tree[pos];         pos -= pos & -pos;     }     return ret; } int add(char *t) {     int n = strlen(t + 1),p = 0;     for(int i = 1;i <= n;++i) {         if(!trie[p][t[i] - 'a']) trie[p][t[i] - 'a'] = ++tot;         p = trie[p][t[i] - 'a'];     }     // printf("!!!%dn",p);     return p; } queue<int>q; vector<int>e[n]; void build() {     for(int i = 0;i < 26;++i) if(trie[0][i]) q.push(trie[0][i]);      while(!q.empty()) {         int u = q.front();q.pop();         e[fail[u]].push_back(u);         for(int i = 0;i < 26;++i) {             if(!trie[u][i]) trie[u][i] = trie[fail[u]][i];             else fail[trie[u][i]] = trie[fail[u]][i],q.push(trie[u][i]);         }     } } void ac_dfs(int u) {     int k = e[u].size();     bh[u] = ++idtot;siz[u] = 1;     for(int i = 0;i < k;++i) {         int v = e[u][i];         ac_dfs(v);         siz[u] += siz[v];     } } int getans(int p) {     // printf("!!!%d %dn",bh[p] + siz[p] - 1,bh[p]);     return query(bh[p] + siz[p] - 1) - query(bh[p] - 1); } void dfs(int u,int p) {     p = trie[p][s[u] - 'a'];     // if(u == 2) printf("!!!%dn",u);          update(bh[p],1);     // printf("!!%d %dn",u,s[u] - 'a');     // printf("!!!%d %dn",u,p);     for(int i = head[u];i;i = e[i].nxt) dfs(e[i].v,p);          int k = que[u].size();     for(int i = 0;i < k;++i) ans[que[u][i].second] = getans(que[u][i].first);      update(bh[p],-1);  } int main() {     int n = read();     for(int i = 1;i <= n;++i) {         int opt = read();         if(opt == 2) fa[i] = read();         add(fa[i],i);         // cin>>s[i];         scanf("%s",&s[i]);     }      int m = read();     for(int i = 1;i <= m;++i) {         int id = read();         scanf("%s",ss + 1);         que[id].push_back(make_pair(add(ss),i));     }      build();      // for(int i = 0;i < 26;++i) printf("!!%dn",trie[0][i]);      // for(int i = 1;i <= tot;++i) printf("!!%dn",fail[i]);      // printf("!!%dn",trie[1][0]);      ac_dfs(0);      // printf("!!!%d %dn",tot,idtot);      for(int i = 1;i <= n;++i) if(!fa[i]) dfs(i,0);            for(int i = 1;i <= m;++i) printf("%dn",ans[i]);      return 0; }