P3121

发表于 分类于
[USACO15FEB]Censoring G

[USACO15FEB]Censoring G

建好自动机之后开个双栈。一个栈存留下来的字符，一个栈存自动机上经过的节点。

然后每当我们匹配的时候扫到一个完整串，我们就把这个串从整串中剔除。实现起来就是把第一个栈的栈顶往前移 $len$，然后把第二个栈的栈顶也往前移 $len$，然后第二个栈的栈顶就是现在所在的节点，继续匹配即可。

最后把第一个栈输出就是答案。

时间复杂度 $O(|s|+\sum_{i=1}^{n}|t_i|)$。复杂度不太高的原因是这里我们的指针真的回跳了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
}using Ehnaev::read;

const ll N=1e6;

ll n,m,tot,top1,top2;
ll trie[N+5][26],cnt[N+5],st1[N+5],st2[N+5],nxt[N+5],lst[N+5];
char buft[N+5],s[N+5];
char *nowt=buft,*t[N+5];

inline void Ins(char *str) {
  ll len=strlen(str),p=0;
  for(ll k=0;k<len;k++) {
    ll ch=str[k]-'a';if(!trie[p][ch]) trie[p][ch]=++tot;p=trie[p][ch];
  }
  cnt[p]=len;
}

inline ll Del(ll p) {top1-=cnt[p];top2-=cnt[p];return st2[top2];}

inline void AC_Pre() {
  queue<ll> q;
  for(ll c=0;c<26;c++) {
    ll u=trie[0][c];if(u) {nxt[u]=0;lst[u]=0;q.push(u);}
  }
  while(!q.empty()) {
    ll h=q.front();q.pop();
    for(ll c=0;c<26;c++) {
      ll u=trie[h][c];if(!u) {trie[h][c]=trie[nxt[h]][c];continue;}
      q.push(u);ll v=nxt[h];while(v&&!trie[v][c]) v=nxt[v];
      nxt[u]=trie[v][c];lst[u]=cnt[nxt[u]]?nxt[u]:lst[nxt[u]];
    }
  }
}

inline void AC() {
  for(ll i=0,j=0;i<n;i++) {
    ll c=s[i]-'a';j=trie[j][c];
    st1[++top1]=c;st2[++top2]=j;
    if(cnt[j]) {j=Del(j);}
    else {if(lst[j]) j=Del(lst[j]);}
  }
}

int main() {

  scanf("%s",s);n=strlen(s);
  m=read();
  for(ll i=1;i<=m;i++) {
    t[i]=nowt;scanf("%s",t[i]);nowt+=strlen(t[i])+2;Ins(t[i]);
  }

  AC_Pre();AC();

  for(ll i=1;i<=top1;i++) {putchar(st1[i]+'a');}

  return 0;
}