P2414 [NOI2011] 阿狸的打字机

求解多模式串的kmp问题，显然是AC自动机了 那么接下来考虑如何将复杂的问题转化 在insert字符串时，记录下每个节点的父亲 如果遇到'B'操作（删除打印序列中的最后一位），就跳回父亲 如果遇到'P'操作，就记录下这个打印序列 tail数组表示第i个打印序列的最后一位 ed数组表示i节点是哪一个打印序列的最后一位 遇到小写字母时直接插入就好了 但要注意*用son数组将ch数组复制* 因为getfail会改变ch数组，但后面仍需使用之前的值 随后可以发现AC自动机的一个神奇性质： **如果节点A的fail指针指向B，则B对应的字符串一定在A中出现** 有了这一性质，就可以将问题转化为： **在fail树中，以X结束点为根的子树中，有多少个点属于Y** 考虑离线操作 把询问按照y从小到大排序 用邻接表重新构建fail树 然后找到每一个y值对应的区间（就是哪几个询问的y值相同） dfs整棵fail树，找出dfs序和各个子树大小 这样一来，只要钉死“属于Y的节点”这个条件就可以序列统计了 所以dfs整棵trie树，让每一个节点对应的序列点+1（回溯时再-1） 如果这个节点是一个打印序列的结尾，那么就找出关于这个节点的询问**区间求和** 显然可以用树状数组了~~（然而还是要抄题解）~~ ~~用结构体封装一下还是比较清晰的~~ ```cpp #include<cstdio> #include<cstring> #include<cctype> #include<queue> #include<algorithm> #define reg register #define reset(a) memset((a),0,sizeof(a)) using namespace std; const int N=1e5+5; char p[N]; struct edge { int to,nxt; }edge[N<<1]; struct question { int x,y,id,ans; }g[N]; int n,num,head[N],idx[N],tot[N],l[N],r[N]; struct Aho_Corasick_automation { int ch[N][26],son[N][26],tail[N],ed[N],fail[N],f[N],cnt,val[N]; inline void clear() { reset(ch); reset(son); reset(fail); reset(f); reset(val); cnt=0; } inline void insert(char *s) { int u=0,len=strlen(s); for (reg int i=0;i<len;i++) { if (s[i]=='B') u=f[u]; else if (s[i]=='P') { tail[++n]=u; ed[u]=n; } else { int v=s[i]-'a'; if (!ch[u][v]) { son[u][v]=ch[u][v]=++cnt; f[ch[u][v]]=u; } u=ch[u][v]; } } } inline void getfail() { queue<int>q; for (reg int i=0;i<26;i++) { int v=ch[0][i]; if (v) q.push(v); } while (!q.empty()) { int u=q.front(); q.pop(); for (reg int i=0;i<26;i++) { int v=ch[u][i]; if (v) q.push(v),fail[v]=ch[fail[u]][i]; else ch[u][i]=ch[fail[u]][i]; } } } }AC; struct Treearray { int c[N<<1]; inline int lowbit(int x){return x&(-x);} inline void add(int x,int p) { while (x<=num) { c[x]+=p; x+=lowbit(x); } } inline int sum(int x) { int res=0; while (x) { res+=c[x]; x-=lowbit(x); } return res; } }T; inline int read() { int x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=-1; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*w; } inline void add_edge(int from,int to) { edge[++num].nxt=head[from]; edge[num].to=to; head[from]=num; } bool cmp(question a,question b) { return a.y<b.y; } bool cmp2(question a,question b) { return a.id<b.id; } void dfs1(int k) { idx[k]=++num; tot[k]=1; for (reg int i=head[k];i;i=edge[i].nxt) { int v=edge[i].to; if (!idx[v]) { dfs1(v); tot[k]+=tot[v]; } } } void dfs2(int k) { T.add(idx[k],1); if (AC.ed[k]) for (reg int i=l[AC.ed[k]];i<=r[AC.ed[k]];i++) { int now=AC.tail[g[i].x]; g[i].ans=T.sum(idx[now]+tot[now]-1)-T.sum(idx[now]-1); } for (reg int i=0;i<26;i++) if (AC.son[k][i]) dfs2(AC.son[k][i]); T.add(idx[k],-1); } int main() { scanf("%s",p); AC.clear(); AC.insert(p); AC.getfail(); int m=read(); for (reg int i=1;i<=m;i++) g[i].x=read(),g[i].y=read(),g[i].id=i; sort(g+1,g+m+1,cmp); for (reg int i=1;i<=AC.cnt;i++) { add_edge(AC.fail[i],i); add_edge(i,AC.fail[i]); } int now=1; for (reg int i=1;i<=m;i=now) { l[g[i].y]=i; while (g[now].y==g[i].y) ++now; r[g[i].y]=now-1; } num=0; dfs1(0); dfs2(0); sort(g+1,g+m+1,cmp2); for (reg int i=1;i<=m;i++) printf("%d\n",g[i].ans); return 0; } ```