最近做题成双成对？不是双倍经验就是两题同解。

   

给定字典，给定字符串，删去字符串中所有字典内单词。保证不会出现二者包含状况。$n \leq 1e5,\sum len \leq 1e5$

AC自动机裸题。build出AC自动机后从左到右插入文本串，同时边匹配边push进栈里。匹配成功就弹栈。

注意要记录匹配到第几个字符的时候，AC自动机指针（我管那个一直蹦的东西就叫指针了？）指到哪里。弹栈之后要指针也要跳回来。

#include
     
      #define x first#define y secondusing namespace std;typedef pair
      
        P;const int N=100010;struct ACAM{    int ch[N][26],cnt[N],f[N];    int sz,rt;    void init(){        memset(ch,-1,sizeof ch);        memset(cnt,0,sizeof cnt);        memset(f,0,sizeof f);        sz=rt=0;    }    void ins(char *s){        int n=strlen(s),u=rt;        for(int i=0;i
       

q; while(!q.empty())q.pop(); for(int i=0;i<26;i++) if(~ch[rt][i]) f[ch[rt][i]]=rt,q.push(ch[rt][i]); else ch[rt][i]=rt; while(!q.empty()){ int u=q.front();q.pop(); for(int i=0;i<26;i++){ int v=ch[u][i]; if(~v){ int now=f[u]; while(f&&!~ch[now][i])now=f[now]; f[v]=ch[now][i];q.push(v); } else ch[u][i]=ch[f[u]][i]; } } } void query(char *s){ int n=strlen(s); stack

S;int u=0; while(!S.empty())S.pop(); for(int i=0;i

ans; while(!S.empty()) ans.push_back(S.top().x+'a'),S.pop(); for(int i=ans.size()-1;~i;i--) printf("%c",ans[i]); }}Aho;char str[N],s[N];int main(){ scanf("%s",str); int n;scanf("%d",&n); Aho.init(); for(int i=1;i<=n;i++){ memset(s,0,sizeof s); scanf("%s",s); Aho.ins(s); } Aho.build(); Aho.query(str);}