string（AC自动机 在线询问转离线询问）
：链接：https://ac.nowcoder.com/acm/problem/14612?&headNav=acm
来源：牛客网
Bob has a dictionary with N words in it. There are M operators. Each operator is one of two kinds.
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
1. Add a string to the dictionary. It is guaranteed that the string s was not added before.
2. For the given string s find the number of occurrences of the strings from the dictionary. If some string p from the dictionary has several occurrences in s you should count all of them.
题目大意：首先是T组测试样例，然后先输入n个字符串放在仓库中，然后m次询问，每一次询问有两种类型。类型1是在仓库中新添加一个字符串。类型2是输入一个字符串，然后问当前仓库中有多少字符串是你操作2输入的字符串的子串。
具体思路：一开始是按照在输入新的n个字符串之后建立fail树的，然后每次查询的时候再重新建立一颗fail树（因为考虑到会添加许多新的字符串），然后就T了。既然询问次数达到了1e5.我们就可以考虑在线的强制转换为离线的算法。（多谢旭伟的提醒）
我们先将所有的字符串输入进来，然后再去建fail树。对于每次操作2，我们从输入的顺序倒着来。在初始输入阶段中，当为操作1时，我们保存当前字符串在trie树上的结尾下标。当全部输入完的
时候，倒序查询，每查询完一个，就将这个操作下面添加的字符串操作在trie树上的权值下标取消就好了。
AC代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 # define ll long long 4 # define inf 0x3f3f3f3f 5 const int maxn = 2e5+100; 6 string str; 7 int tot,ch[maxn][30],val[maxn]; 8 int fail[maxn],last[maxn]; 9 struct node 10 { 11 int type; 12 int end_pos; 13 string str; 14 node() {} 15 node(int xx,int yy) 16 { 17 type=xx,end_pos=yy; 18 } 19 } q[maxn]; 20 int sto[maxn]; 21 int add() 22 { 23 int p=0; 24 int len=str.size(); 25 for(int i=0; i<len; i++) 26 { 27 int u= str[i]-'a'; 28 if(!ch[p][u]) 29 ch[p][u]=++tot; 30 p=ch[p][u]; 31 } 32 val[p]++; 33 return p; 34 } 35 void getfail() 36 { 37 queue<int>q; 38 for(int i=0;i<=tot;i++)fail[i]=-1; 39 q.push(0); 40 while(!q.empty()) 41 { 42 int top=q.front(); 43 q.pop(); 44 for(int i=0; i<26; i++) 45 { 46 int u=ch[top][i]; 47 if(u==0) 48 continue; 49 q.push(u); 50 int v=fail[top]; 51 while(v!=-1&&!ch[v][i]) 52 v=fail[v]; 53 fail[u]=(v==-1?0:ch[v][i]); 54 last[u]=val[fail[u]]?fail[u]:last[fail[u]]; 55 } 56 } 57 } 58 void init() 59 { 60 for(int i=0; i<=tot; i++) 61 { 62 fail[i]=0,last[i]=0,val[i]=0; 63 for(int j=0; j<30; j++) 64 { 65 ch[i][j]=0; 66 } 67 } 68 tot=0; 69 } 70 int cal(int t) 71 { 72 int ans=0; 73 while(t) 74 { 75 ans+=val[t]; 76 t=last[t]; 77 } 78 return ans; 79 } 80 int getans(string st) 81 { 82 int ans=0; 83 int len=st.size(); 84 85 int p=0; 86 for(int i=0; i<len; i++) 87 { 88 int u=st[i]-'a'; 89 while(p&&ch[p][u]==0) 90 p=fail[p]; 91 p=ch[p][u]; 92 if(val[p]) 93 ans+=cal(p); 94 else if(fail[p]) 95 { 96 ans+=cal(fail[p]); 97 } 98 } 99 return ans; 100 } 101 int main() 102 { 103 ios::sync_with_stdio(false); 104 int T; 105 cin>>T; 106 //scanf("%d",&T); 107 while(T--) 108 { 109 init(); 110 int n,m; 111 cin>>n>>m; 112 //scanf("%d %d",&n,&m); 113 for(int i=1; i<=n; i++) 114 { 115 cin>>str; 116 // scanf("%s",str); 117 add(); 118 } 119 getfail(); 120 int type; 121 int num=0; 122 while(m--) 123 { 124 cin>>type>>str; 125 //scanf("%d%s",&type,str); 126 if(type==1) 127 { 128 q[++num].type=1; 129 q[num].end_pos=add(); 130 } 131 else 132 { 133 q[++num].type=2; 134 q[num].str=str; 135 } 136 } 137 getfail(); 138 for(int i=num; i>=1; i--) 139 { 140 if(q[i].type==2) 141 sto[i]=getans(q[i].str); 142 else 143 { 144 val[q[i].end_pos]--; 145 } 146 } 147 for(int i=1; i<=num; i++) 148 { 149 if(q[i].type==2) 150 cout<<sto[i]<<endl; 151 } 152 } 153 return 0; 154 }
