免费毕业设计的网站建设,同制作网站一样都是在,做自己的网站服务器多少钱,烟台艺术学校官网ACM模板 目录插入以及构建AC自动机【模板】AC自动机#xff08;二次加强版#xff09;ac自动机fail树上dfs序建可持久化线段树插入以及构建AC自动机
#includequeue
#includestring
const int N200010;
struct node
{int chd[26],fail,cnt;
}tree[N];
void i…ACM模板 目录插入以及构建AC自动机【模板】AC自动机二次加强版ac自动机fail树上dfs序建可持久化线段树插入以及构建AC自动机
#includequeue
#includestring
const int N200010;
struct node
{int chd[26],fail,cnt;
}tree[N];
void insert(string s)
{int p0;for(int i0;is.size();i){int cs[i]-a;if(!tree[p].chd[c]) tree[p].chd[c]cnt;ptree[p].chd[c];}
}
void build()
{queueint q;for(int i0;i26;i)if(tree[0].chd[i]) q.push(tree[0].chd[i]);while(q.size()){int tq.front();q.pop();for(int i0;i26;i){int chdtree[t].chd[i];if(chd)tree[chd].failtree[tree[t].fail].chd[i],q.push(chd);else// 如果没有儿子 那么将fail的儿子作为儿子chdtree[tree[t].fail].chd[i];}}
}【模板】AC自动机二次加强版
给你一个文本串 SSS 和 nnn 个模式串 T1..nT_{1..n}T1..n请你分别求出每个模式串 TiT_iTi 在 SSS 中出现的次数。
#includequeue
#includestring
#includecstring
#includeiostream
using namespace std;
const int N200010;
struct node
{int chd[26],fail,cnt;
}tree[N];
int cnt;
int h[N],e[N],ne[N],idx;
int pos[N];
void add(int a,int b)
{e[idx]b,ne[idx]h[a],h[a]idx;
}
int insert(string s)
{int p0;for(int i0;is.size();i){int cs[i]-a;if(!tree[p].chd[c]) tree[p].chd[c]cnt;ptree[p].chd[c];}return p;
}
void build()
{queueint q;for(int i0;i26;i){int ctree[0].chd[i];if(!c) continue;tree[c].fail0;add(0,c);q.push(c);}while(q.size()){int tq.front();q.pop();for(int i0;i26;i){int chdtree[t].chd[i];if(chd){tree[chd].failtree[tree[t].fail].chd[i];add(tree[chd].fail,chd);// 构建失配树 fail指针向自己连边q.push(chd);}elsechdtree[tree[t].fail].chd[i];}}
}
void dfs(int u)
{for(int ih[u];i!-1;ine[i]){int je[i];dfs(j);tree[u].cnttree[j].cnt;}
}
int main()
{ios::sync_with_stdio(0);memset(h,-1,sizeof h);int n;cinn;string s;for(int i1;in;i){cins;pos[i]insert(s);}build();cins;for(int i0,j0;is.size();i){jtree[j].chd[s[i]-a];tree[j].cnt;}dfs(0);for(int i1;in;i) couttree[pos[i]].cnt\n;return 0;
}ac自动机fail树上dfs序建可持久化线段树
待更新 upd:2020/2/2 子串能够表示为前缀的后缀在Trie树中经过的节点是前缀fail树上是后缀
#includequeue
#includestring
#includecstring
#includeiostream
#includealgorithm
using namespace std;
constexpr int N200010;
struct node1
{int chd[26],fail,fa;int id;
}tree[N];int idx1;
int h[N],e[N],ne[N],idx2;
int n,m,pos[N];
void add(int a,int b){e[idx2]b,ne[idx2]h[a],h[a]idx2;}
void insert(string s,int id)
{int p0;for(int i0;is.size();i){int chdtree[p].chd[s[i]-a];if(!chd) {chdidx1;tree[chd].fap;}pchd;}tree[p].idid;pos[id]p;
}
void build()
{queueint q;for(int i0;i26;i){int chdtree[0].chd[i];if(!chd) continue;q.push(chd);}while(q.size()){int tq.front();q.pop();add(tree[t].fail,t); //建fail树for(int i0;i26;i){int chdtree[t].chd[i];if(chd)tree[chd].failtree[tree[t].fail].chd[i],q.push(chd);elsechdtree[tree[t].fail].chd[i];}}
}
struct node2
{int l,r;int val;
}T[40*N];
int root[N],cnt;
void update(int l,int r,int pre,int now,int pos,int val)
{nowcnt;T[now]T[pre];T[now].valval;if(lr) return;int midlr1;if(posmid) update(l,mid,T[pre].l,T[now].l,pos,val);elseupdate(mid1,r,T[pre].r,T[now].r,pos,val);
}
int query(int u,int l,int r,int L,int R)
{if(!u) return 0;if(LlrR) return T[u].val;int midlr1;int v0;if(Lmid) vquery(T[u].l,l,mid,L,R);if(Rmid) vquery(T[u].r,mid1,r,L,R);return v;
}
int dfn[N],sz[N],timestamp;
void dfs(int u)
{dfn[u]timestamp;sz[u]1;for(int ih[u];i!-1;ine[i]){int je[i];dfs(j);sz[u]sz[j];}
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cinnm;memset(h,-1,sizeof h);for(int i1;in;i){string s;cins;insert(s,i);}build();dfs(0);// dfs序for(int i1;in;i) {update(1,timestamp,root[i-1],root[i],dfn[pos[i]],1);int ptree[pos[i]].fa;while(p){update(1,timestamp,root[i],root[i],dfn[p],1);ptree[p].fa;}}while(m--){int l,r,k;cinlrk;coutquery(root[r],1,timestamp,dfn[pos[k]],dfn[pos[k]]sz[pos[k]]-1)-query(root[l-1],1,timestamp,dfn[pos[k]],dfn[pos[k]]sz[pos[k]]-1)\n;}return 0;
}
