200行代码。。
题意:给一些模式串和q次操作,每次可以把一个新匹配串扔进一个集合里,或者询问当前集合里所有匹配串有几个包含某模式串。
题解:首先是多模匹配,把模式串全扔到ac自动机上,建fail树。
对于操作一:匹配串扔进去后会对经过的所有节点与父节点的链上有贡献。而且就算多次跑到同一个点,由于是同一个匹配串,最多贡献只能计算为1,那么转化为在fail树上的一些点,往他们与根结点的链交集上加一。询问的时候只询问一个节点的值,链交上所有点都更新的话代价太大,考虑转化成树上差分+求带修的子树和,做法是:跑出fail树的dfs序,在链交集上把所有节点按dfs序排序,然后把所有节点权值+1,相邻节点的lca处权值-1,这样的树上差分操作才能保证正确(!)。
对于操作二:只需按dfs序建立线段树,维护权值,允许单点加减和区间查询(dfs序号到dfs+siz即为子树和)。
#include <bits/stdc++.h> using namespace std; #define ll long long const int maxn=2e6+10; int n,cnt=1,tot; struct aczdj{ int vis[30],fail,ans1; int end; }ac[maxn]; int mp[maxn],rd[maxn],dfn[maxn],rdfn[maxn],siz[maxn]; vector<int> yuan[maxn]; void build1(string now,int biao){ int now1=now.length(),now2=1; for(int i=0;i<now1;i++){ int v=now[i]-'a'+1; if(!ac[now2].vis[v]){ ac[now2].vis[v]=++cnt; } now2=ac[now2].vis[v]; } ac[now2].end=biao; mp[biao]=now2; } void buildfail(){ queue<int> k1; for(int i=1;i<=26;i++) ac[0].vis[i]=1; k1.push(1); while(!k1.empty()){ int tmp=k1.front();k1.pop(); int fl=ac[tmp].fail; for(int i=1;i<=26;i++){ int v=ac[tmp].vis[i]; if(!v) ac[tmp].vis[i]=ac[fl].vis[i]; else{ ac[v].fail=ac[fl].vis[i]; yuan[ac[fl].vis[i]].push_back(v); rd[v]++; k1.push(v); } } } } int dep[maxn],fat[maxn][60],lg[maxn]; void dfs(int now,int fa){ dfn[now]=++tot;rdfn[tot]=now; siz[now]=1; dep[now]=dep[fa]+1; fat[now][0]=fa; for(int i=1;i<=lg[dep[now]];i++) fat[now][i]=fat[fat[now][i-1]][i-1]; for(int i=0;i<yuan[now].size();i++){ int v=yuan[now][i]; if(v==fa) continue; dfs(v,now); siz[now]+=siz[v]; } } int lca(int u,int v){ if(dep[u]>dep[v]) swap(u,v); while(dep[v]>dep[u]) v=fat[v][lg[dep[v]-dep[u]]-1]; if(u==v) return u; for(int i=lg[dep[v]];i>=0;i--){ if(fat[u][i]!=fat[v][i]){ u=fat[u][i]; v=fat[v][i]; } } return fat[v][0]; } struct node{ int zhi; }all[maxn*4]; void pushup(int now){all[now].zhi=all[now*2].zhi+all[now*2+1].zhi;} void build(int now,int lo,int ro){ if(lo==ro) return; build(now*2,lo,mid); build(now*2+1,mid+1,ro); } void upd(int now,int lo,int ro,int pos,int zhi){ if(lo==ro&&lo==pos){ all[now].zhi+=zhi; return; } if(pos<=mid) upd(now*2,lo,mid,pos,zhi); else upd(now*2+1,mid+1,ro,pos,zhi); pushup(now); } void acque(string &now){ vector<int> k2; int now1=now.length(),now2=1; for(int i=0;i<now1;i++){ int v=now[i]-'a'+1; now2=ac[now2].vis[v]; k2.push_back(dfn[now2]); } sort(k2.begin(),k2.end()); for(int i=0;i<k2.size();i++){ if(i&&k2[i]==k2[i-1]) continue; upd(1,1,tot,k2[i],1); if(i){ int fat1=lca(rdfn[k2[i]],rdfn[k2[i-1]]); upd(1,1,tot,dfn[fat1],-1); } } } ll req(int now,int lo,int ro,int lo1,int ro1){ if(lo>=lo1&&ro<=ro1){ return all[now].zhi; } if(lo>ro1||ro<lo1) return 0; ll ans1=0; if(mid>=lo1) ans1+=req(now*2,lo,mid,lo1,ro1); if(mid<ro1) ans1+=req(now*2+1,mid+1,ro,lo1,ro1); return ans1; } signed main(){ for(int i=1;i<=2e6;i++){ lg[i]=lg[i-1]; if(i==(1<<lg[i])) lg[i]++; } cin>>n;string yuan1; for(int i=1;i<=n;i++){ cin>>yuan1; build1(yuan1,i); } buildfail(); dfs(1,0); build(1,1,tot); int q;cin>>q; while(q--){ int a1,a2;cin>>a1; if(a1==1){ string p1;cin>>p1; acque(p1); } else{ cin>>a2; cout<<req(1,1,tot,dfn[mp[a2]],dfn[mp[a2]]+siz[mp[a2]]-1)<<endl; } } return 0; }