noip2019集训测试赛（一）B.字符串

Description

UPD:本题字符集为全体小写字母

Input

Output

Solution

这题我写了一个查询前暴力get_fail的，复杂度爆炸，但数据水，过了

时间复杂度：O(mlogm)

正解是用所有的s建AC自动机，再建fail树，最后用树状数组维护各种字符串的个数（假的强制在线）。

前序遍历fail树，得到dfn，就可以愉快地维护树状数组查询答案了~

关于fail树可以看看这里：https://blog.csdn.net/niiick/article/details/87947160

tips:把查询的s也插入AC自动机其实对解题没有影响，因为最后统计的实际是每个操作1和操作2对某段区间的贡献，即某段区间的点代表的字符串都包含该串。

但是实际上出题人的意思是通过二进制分组，建立$logm$个AC自动机，使用类似启发式合并的方法将size相同的AC自动机合并，这样每个字符串最多被插入$logm$次，时间复杂度O(mlogm)。（想想就觉得不会打麻烦）

Code

给的是某位AK比赛的学长的代码，rp++

#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=2000005;
int m,l,tot=1,len[N],bg[N],fail[N],num[N],ch[N][26];
int cnt,idx,nt,head[N],to[N],nxt[N],dfn[N],siz[N],ck[N];
ll c[N],mask,ans,val[N],op[N];
char s[N],str[N];
void adde(int u,int v){to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
}
void insert(char s[],int id){int k=1;for(int i=0;i<len[id];i++){int x=s[i]-'a';if(!ch[k][x]){ch[k][x]=++tot;}k=ch[k][x];}num[id]=k;
}
void build(){queue<int> q;q.push(1);while(!q.empty()){int u=q.front();q.pop();for(int i=0;i<26;i++){int p=u==1?1:ch[fail[u]][i];if(ch[u][i]){fail[ch[u][i]]=p;q.push(ch[u][i]);}else{ch[u][i]=p;}}}for(int i=2;i<=tot;i++){adde(fail[i],i);}
}
void dfs(int u){dfn[u]=++idx;siz[u]=1;int v;for(int i=head[u];i;i=nxt[i]){v=to[i];dfs(v);siz[u]+=siz[v];}
}
void add(int i,int v){for(;i<=idx;i+=i&(-i)){c[i]+=v;}
}
ll query(int i){ll res=0;for(;i;i-=i&(-i)){res+=c[i];}return res;
}
void go(int l,int r){nt++;int k=1;for(int i=l;i<=r;i++){int x=s[i]-'a';k=ch[k][x];if(cxk[k]==nt){//cxk仅仅用于卡常 CXKNMSL(雾ans+=val[k];}else{cxk[k]=nt;val[k]=query(dfn[k]);ans+=val[k];}}
}
int main(){scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%lld%s",&op[i],str);len[i]=strlen(str);bg[i]=l+1;insert(str,i);for(int j=0;j<len[i];j++){s[++l]=str[j];}}build();dfs(1);for(int i=1;i<=m;i++){op[i]^=mask;if(op[i]==1){add(dfn[num[i]],1);add(dfn[num[i]]+siz[num[i]],-1);}else if(op[i]==2){add(dfn[num[i]],-1);add(dfn[num[i]]+siz[num[i]],1);}else{ans=0;go(bg[i],bg[i]+len[i]-1);printf("%lld\n",ans);mask^=labs(ans);}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！