AC自动机以trie为基础，首先将若干模式串插入trie树中，之后构建fail指针和AC自动机，即由trie树变为trie图。
fail指针的定义是，对于当前点x，从根到x形成的字符串为s，x的fail指针指向y，其中满足根到y形成的字符串t是s的最长后缀。
BFS构建AC自动机，第二层的所有节点的fail指针都要指向trie树的根节点。
通过修改trie树的结构，增加了转移关系，避免构建时一直while跳fail。
对于通配符，若一种通配符可以匹配无数多个字符，那么将该点向自己连边形成自环即可。
struct ACAutomaton{
struct tree{
int ch[26],fail,cnt;
}t[N];
int tot,root;
#define ch(p,x) (t[p].ch[x])
#define f(p) (t[p].fail)
#define c(p) (t[p].cnt)
inline void insert(string s){
int p=root,n=s.size();
for(int i=0;i<n;i++){
int c=s[i]-'a';
if(!ch(p,c))ch(p,c)=++tot;
p=ch(p,c);
}
c(p)++;/*当前字符串出现次数*/
}
inline void makefail(){
queue<int>q;
for(int i=0;i<26;i++)if(ch(root,i))q.emplace(ch(root,i));/*第二层所有节点入队*/
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=0;i<26;i++){
if(ch(x,i)){/*如果存在该子节点*/
f(ch(x,i))=ch(f(x),i);/*子节点的fail是当前点fail对应的相同子节点*/
q.emplace(ch(x,i));/*之后入队*/
}
else ch(x,i)=ch(f(x),i);/*子节点指向当前点fail的对应子节点*/
}
}
}
inline int count(string s){/*询问trie树中的字符串在s中出现的个数*/
int p=root,n=s.size(),re=0;
for(int i=0;i<n;i++){
int c=s[i]-'a';
p=ch(p,c);/*在trie树上跳*/
for(int j=p;j&&c(j)!=-1;j=f(j)){/*一个点可以匹配成功，则它的fail也可以匹配成功*/
re+=c(j);
c(j)=-1;/*标记已经加过了*/
}
}
return re;
}
};
给定一些模式串和一个文本串，求在文本串中出现次数最多的模式串出现的次数和这些串的内容。在构建trie树时维护是哪一个串，插入时在字符串末尾节点标记一下，查询的时候暴力跳fail并对这个节点表示的id的答案累加，不标记访问，找出每个id对应ans的最大值即可，注意不要直接对ans进行更新，只有当节点是某个字符串末尾时才进行更新。
struct tree{
int ch[26],fail,idx;
inline void clear(){
memset(this,0,sizeof(*this));
}
}t[N];
int tot,root;
#define ch(p,x) (t[p].ch[x])
#define f(p) (t[p].fail)
#define i(p) (t[p].idx)
inline void insert(string s,int idx){
int p=root,n=s.size();
for(int i=0;i<n;i++){
int c=s[i]-'a';
if(!ch(p,c))ch(p,c)=++tot;
p=ch(p,c);
}
i(p)=idx;
}
inline void query(string s){
int p=root,n=s.size();
for(int i=0;i<n;i++){
int c=s[i]-'a';
p=ch(p,c);
for(int j=p;j;j=f(j)){
if(i(j)==0)continue;
res[i(j)]++;
ans=max(ans,res[i(j)]);
}
}
}
求每个模式串在文本串中出现的次数。在建出fail树后，记录自动机上每个状态被匹配了多少次，求出每个文本串在fail树上的终止点的子树和即可。由于fail树是由一个点的fail指向的点向该点连边，在bfs时父节点都是先被遍历到，所以可以不用构建fail树，直接从最后入队的节点开始向前扫，自己fial的次数累加上自己的次数，这样的话就最好手写队列。
struct tree{
int ch[26],fail,sum;
}t[N];
int tot,root,pos[N],q[N],l=1,r=0;
#define ch(p,x) (t[p].ch[x])
#define f(p) (t[p].fail)
#define s(p) (t[p].sum)
inline void insert(string s,int id){
int p=root,n=s.size();
for(int i=0;i<n;i++){
int c=s[i]-'a';
if(!ch(p,c))ch(p,c)=++tot;
p=ch(p,c);
}
pos[id]=p;
}
inline void makefail(){
l=1,r=0;
for(int i=0;i<26;i++)if(ch(root,i))q[++r]=(ch(root,i));
while(l<=r){
int x=q[l++];
for(int i=0;i<26;i++){
if(ch(x,i)){
f(ch(x,i))=ch(f(x),i);
q[++r]=(ch(x,i));
}
else ch(x,i)=ch(f(x),i);
}
}
}
inline void query(string s){
int p=root,n=s.size();
for(int i=0;i<n;i++){
int c=s[i]-'a';
p=ch(p,c);
s(p)++;
}
for(int i=r;i;i--)s(f(q[i]))+=s(q[i]);
}
inline int find(int x){
return s(pos[x]);
}
给定一个列表和一个文本串s，每次删除列表中最早出现在s中的单词，求最后的s.维护两个栈，在AC自动机上匹配s时，若匹配成功，则将栈顶跳到匹配该单词之前，也就是减去这个单词的长度，一个栈维护trie树上的节点，一个栈维护对应的下标。
struct tree{
int ch[26],fail,len;
}t[N];
int tot,root,top;
pair<int,int>stk[N];
#define ch(p,x) (t[p].ch[x])
#define f(p) (t[p].fail)
#define l(p) (t[p].len)
inline void insert(string s){
int p=root,n=s.size();
for(int i=0;i<n;i++){
int c=s[i]-'a';
if(!ch(p,c))ch(p,c)=++tot;
p=ch(p,c);
}
l(p)=n;
}
inline void solve(string s){
int p=root,n=s.size();
for(int i=0;i<n;i++){
int c=s[i]-'a';
p=ch(p,c);
stk[++top]={p,i};
p=stk[top-=l(p)].first;/*如果不是一个字符串的末尾时l(p)=0，相当于没有变动*/
}
for(int i=1;i<=top;i++)cout<<s[stk[i].second];
}
支持三种操作，添加编号为i的字符串，删除编号为i的字符串，查询已有字符串集合中的字符串在询问的文本串中出现的次数，添加时若已有应忽略，删除时若已经没有应忽略。构建fail树后，找到当前字符串的结尾节点，删除操作就是在该节点的子树内全部减一，添加就是全部加一，查询时就是对文本串在trie树上跑，每个点累加子树和，可以用树状数组去检修盖单点查询维护。
struct tree{
int ch[26],fail,fa;
}t[N];
int tot,root,pos[N],ipt[N],opt[N],dfn;
#define ch(p,x) (t[p].ch[x])
#define f(p) (t[p].fail)
inline void insert(string s,int idx){
int p=root,n=s.size();
for(int i=0;i<n;i++){
int c=s[i]-'a';
if(!ch(p,c))ch(p,c)=++tot;
p=ch(p,c);
}
pos[idx]=p;
}
inline void makefail(){
queue<int>q;
for(int i=0;i<26;i++)if(ch(root,i))q.emplace(ch(root,i)),v[root].emplace_back(ch(root,i));
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=0;i<26;i++){
if(ch(x,i)){
f(ch(x,i))=ch(f(x),i);
q.emplace(ch(x,i));
v[f(ch(x,i))].emplace_back(ch(x,i));
}
else ch(x,i)=ch(f(x),i);
}
}
}
void dfs(int x){
ipt[x]=++dfn;
for(auto y:v[x])dfs(y);
opt[x]=dfn;
}
inline int query(string s){
int p=root,n=s.size(),re=0;
for(int i=0;i<n;i++){
int c=s[i]-'a';
p=ch(p,c);
re+=bit.ask(ipt[p]);
}
return re;
}
aca.dfs(0);
bit.n=aca.dfn;
for(int i=1;i<=n;i++)bit.add(aca.ipt[aca.pos[i]],aca.opt[aca.pos[i]],1);
while(q--){
string s;
cin>>s;
if(s[0]=='?'){
cout<<aca.query(s)<<'\n';
continue;
}
int j=0,x=0;
while(s[++j])x=(x<<1)+(x<<3)+(s[j]^48);
if(s[0]=='-'&&!del[x]){
del[x]=1;
bit.add(aca.ipt[aca.pos[x]],aca.opt[aca.pos[x]],-1);
}
else if(s[0]=='+'&&del[x]){
del[x]=0;
bit.add(aca.ipt[aca.pos[x]],aca.opt[aca.pos[x]],1);
}
}