题目描述
原题来自: USACO 2015 Feb. Gold
有一个长度不超过 10510^5105 的字符串 SSS.Farmer John 希望在 SSS 中删掉 nnn 个屏蔽词 (一个屏蔽词可能出现多次), 这些词记为 t1tnt_1\sim t_nt1?tn?.
FJ 在 SSS 中从头开始寻找屏蔽词, 一旦找到一个屏蔽词, FJ 就删除它, 然后又从头开始寻找 (而不是接着往下找).FJ 会重复这一过程, 直到 SSS 中没有屏蔽词为止. 注意删除一个单词后可能会导致 SSS 中出现另一个屏蔽词. 这 nnn 个屏蔽词不会出现一个单词是另一个单词子串的情况, 这意味着每个屏蔽词在 SSS 中出现的开始位置是互不相同的, 请帮助 FJ 完成这些操作并输出最后的 SSS.
输入格式
第一行包含一个字符串 SSS;
第二行包含一个整数 nnn;
接下来的 nnn 行, 每行包含一个字符串, 第 iii 行的字符串是 tit_iti?.
输出格式
一行, 输出操作后的 SSS. 保证 SSS 不会变成空串.
样例
样例输入
- begintheescapexecutionatthebreakofdawn
- 2
- escape
- execution
样例输出
beginthatthebreakofdawn
第一眼看到, 以为是 bzoj3942, 然后就被 dalao 鄙视了
但是这道题的思想和那道题很像, 只不过是把操作过程中的 KMP 换成了 AC 自动机
只需要在匹配成功后出栈, 中级记录一个可持久化的数组, 用来存出栈后从 Trie 树的那个节点开始重新匹配
下面给出代码:
- #include<iostream>
- #include<algorithm>
- #include<cstdio>
- #include<cstdlib>
- #include<cstring>
- #include<string>
- #include<cmath>
- using namespace std;
- inline int rd(){
- int x=0,f=1;
- char ch=getchar();
- for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
- for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
- return x*f;
- }
- inline void write(int x){
- if(x<0) putchar('-'),x=-x;
- if(x>9) write(x/10);
- putchar(x%10+'0');
- return ;
- }
- char s[1000006];
- char a[1000006];
- int n,len=0;
- int trie[1000006][30];
- int tot=1;
- int vis[1000006];
- void pre(){
- int c=1;
- for(int i=1;i<=len;i++){
- int h=a[i]-'a';
- if(!trie[c][h]) trie[c][h]=++tot;
- c=trie[c][h];
- }
- vis[c]=len;
- return ;
- }
- int nxt[1000006];
- int q[1000006];
- int l=0,r=0;
- void get_next(){
- q[++r]=1;
- for(int i=0;i<=25;i++) trie[0][i]=1;
- nxt[1]=0;
- while(l<r){
- int h=q[++l];
- for(int i=0;i<=25;i++){
- if(!trie[h][i]) trie[h][i]=trie[nxt[h]][i];
- else{
- nxt[trie[h][i]]=trie[nxt[h]][i];
- q[++r]=trie[h][i];
- }
- }
- }
- return ;
- }
- int sk[1000006];
- int cnt=0;
- int loc[1000006];
- void solve(){
- int m=strlen(s+1);
- int c=1;
- for(int i=1;i<=m;i++){
- sk[++cnt]=i;
- int h=s[i]-'a';
- int y=trie[c][h];
- if(trie[c][h]){
- if(vis[trie[c][h]]){
- cnt-=vis[trie[c][h]];
- c=loc[sk[cnt]];
- continue;
- }
- }
- c=y;
- loc[i]=y;
- }
- return ;
- }
- int main(){
- scanf("%s",s+1);
- n=rd();
- for(int i=1;i<=n;i++){
- scanf("%s",a+1);
- len=strlen(a+1);
- pre();
- }
- get_next();
- solve();
- for(int i=1;i<=cnt;i++) printf("%c",s[sk[i]]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2797994.html