首页 > 代码库 > bzoj3940[Usaco2015 Feb]Censoring*
bzoj3940[Usaco2015 Feb]Censoring*
bzoj3940[Usaco2015 Feb]Censoring
题意:
有一个S串和一大堆T串，不断地在S串里找最早出现的T串，然后将其删除。S串≤100000，T串总长度≤100000。
题解：
对所有T串建AC自动机，然后同bzoj3942。注意，本题的AC自动机必须利用所有fail函数建成一个大的状态图，否则会超时。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define maxn 100010 7 using namespace std; 8 9 char str[maxn],word[maxn],st1[maxn]; int ch[maxn][26],val[maxn],n,fail[maxn],top,pos,len,st2[maxn],tot;10 inline void insert(char *str){11 int j=0,len=strlen(str+1);12 inc(i,1,len){if(!ch[j][str[i]-‘a‘])ch[j][str[i]-‘a‘]=++tot; j=ch[j][str[i]-‘a‘];} val[j]=len;13 }14 queue <int> q;15 void getfail(){16 inc(i,0,25)if(ch[0][i])q.push(ch[0][i]);17 while(!q.empty()){18 int x=q.front(); q.pop();19 inc(i,0,25){20 int j=ch[fail[x]][i];21 if(ch[x][i]){fail[ch[x][i]]=j; q.push(ch[x][i]);}else{ch[x][i]=j;}22 }23 }24 }25 int main(){26 scanf("%s",str+1); len=strlen(str+1); scanf("%d",&n);27 inc(i,1,n){scanf("%s",word+1); insert(word);} getfail(); top=0; pos=0;28 inc(i,1,len){29 st1[++top]=str[i]; pos=ch[pos][str[i]-‘a‘]; st2[top]=pos; if(val[pos])top-=val[pos],pos=st2[top];30 }31 inc(i,1,top)printf("%c",st1[i]); return 0;32 }
20160901
bzoj3940[Usaco2015 Feb]Censoring*
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。