题目大意：略(太长了不好描述) 良心LOJ传送门
先对所有被打印的字符串建一颗Trie树
观察数据范围，并不能每次打印都从头到尾暴力建树，而是每遍历到一个字符就在Trie上插入这个字符，然后记录每次打印后字符串最后一个字符在Trie树上的位置
然后建立AC自动机，再建立Fail树。注意还要另外存一下原来Trie树的结构
Fail树就是把Fail指针倒着跑，因为每个点只有一个Fail指针，所以最后所有Fail指针会形成一棵树
Fail树有一个神奇的性质，即父节点表示的字符串(从Trie树的根节点一直到这个点所表示的字符串)，一定是子节点表示的字符串的一个后缀
原问题是求x号字符串在y号字符串内出现的次数
问题可以转化为，求x作为后缀，出现在y的所有前缀的次数
根据Fail树的性质：父节点一定是子节点的后缀
那么从Trie根节点到y结尾节点的所有点，都能分别表示y的一个前缀串
而如果x是某个串的后缀，那么这个串一定在x的Fail树的子树内
如果对所有问题暴力匹配x,y又不可取
查询y的所有前缀出现在x子树内的次数，相当于在x子树内求和，貌似可以用DFS序+树状数组优化
我们可以对问题进行离线处理，把问题挂在Trie树上以y的结尾的位置上。然后跑出Fail树DFS序。再在Tire树上跑DFS，搜索到这个节点，就在它dfs序入栈的位置上+1，回溯过这个节点，就-1，这个操作其实是在表示所有可能的y的所有前缀
再回溯过这个节点之前，处理挂在这个点上所有的询问。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 #define idx(x) x-‘a‘+1 6 #define lowbit(x) (x&(-x)) 7 #define N 100100 8 using namespace std; 9 10 char str[N]; 11 int n,m,len,num,cte,ctq,tot,dfn,qs; 12 int use[N],pos[N],head[N],st[N],ed[N],s[N*2],hq[N]; 13 struct Edge{int to,nxt;}edge[N*2],ques[N]; 14 void ae(int u,int v){cte++;edge[cte].to=v,edge[cte].nxt=head[u],head[u]=cte;} 15 void aq(int u,int v){ctq++;ques[ctq].to=v,ques[ctq].nxt=hq[u],hq[u]=ctq;} 16 struct AC{ 17 int fa[N],son[N][28],ch[N][28],fail[N]; 18 int cre(int w,int ff){tot++;fa[tot]=ff;return tot;} 19 void Build() 20 { 21 int x=0; 22 for(int i=1;i<=len;i++) 23 { 24 if(‘a‘<=str[i]&&str[i]<=‘z‘){ 25 int w=idx(str[i]); 26 if(!ch[x][w]) ch[x][w]=son[x][w]=cre(w,x); 27 x=ch[x][w]; 28 }else if(str[i]==‘B‘){ 29 x=fa[x]; 30 }else pos[++num]=x; 31 } 32 } 33 void Fail() 34 { 35 queue<int>q; 36 for(int i=1;i<=26;i++) 37 if(ch[0][i]) q.push(ch[0][i]),ae(0,ch[0][i]); 38 while(!q.empty()) 39 { 40 int x=q.front();q.pop(); 41 for(int i=1;i<=26;i++) 42 if(ch[x][i]){ 43 fail[ch[x][i]]=ch[fail[x]][i]; 44 ae(fail[ch[x][i]],ch[x][i]); 45 q.push(ch[x][i]); 46 }else{ 47 ch[x][i]=ch[fail[x]][i]; 48 } 49 } 50 } 51 void dfs(int u) 52 { 53 st[u]=++dfn; 54 for(int j=head[u];j;j=edge[j].nxt){ 55 int v=edge[j].to; 56 dfs(v); 57 }ed[u]=++dfn; 58 } 59 void main() 60 { 61 Build(); 62 Fail(); 63 dfs(0); 64 } 65 }ac; 66 struct Ques{int x,y,id,ans;}q[N]; 67 void update(int x,int w){for(int i=x;i<=dfn;i+=lowbit(i))s[i]+=w;} 68 int query(int x){int ans=0;for(int i=x;i>0;i-=lowbit(i))ans+=s[i];return ans;} 69 void dfs_ans(int x) 70 { 71 update(st[x],1); 72 for(int i=1;i<=26;i++) 73 { 74 if(ac.son[x][i]) 75 dfs_ans(ac.son[x][i]); 76 } 77 for(int j=hq[x];j;j=ques[j].nxt){ 78 int v=ques[j].to; 79 q[v].ans=query(ed[pos[q[v].x]])-query(st[pos[q[v].x]]-1); 80 } 81 update(ed[x],-1); 82 } 83 84 int main() 85 { 86 scanf("%s",str+1); 87 len=strlen(str+1); 88 ac.main(); 89 int x,y; 90 scanf("%d",&m); 91 for(int i=1;i<=m;i++) 92 { 93 scanf("%d%d",&x,&y); 94 qs++,q[qs].x=x,q[qs].y=y,q[qs].id=i; 95 aq(pos[y],qs); 96 } 97 dfs_ans(0); 98 for(int i=1;i<=m;i++){printf("%d\n",q[i].ans);} 99 return 0; 100 }
NOI 2011 阿狸的打字机 (AC自动机+dfs序+树状数组)
原文：https://www.cnblogs.com/guapisolo/p/9697127.html