题目大意:

自己看.

题解:

利用AC自动机顺序扫描.

在AC自动机上的每个终止节点上记录串的长度.

每当发现完全匹配到某一个串,就将当前状态回退[串的长度]那么多,回到那个节点继续.

实在不懂的就看代码吧.

代码:

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
 
#define N 100010
char s1[N],s2[N];
int tr[N][26],cnt,fail[N],len[N];
bool end[N],del[N];
int stack[N],top,ins[N];
int main(){
    scanf("%s",s1+1);
    int n=strlen(s1+1),i,j,m,_n;
    scanf("%d",&m);
    int p;
    while(m--){
        scanf("%s",s2+1);
        _n=strlen(s2+1);
        for(p=0,i=1;i<=_n;++i){
            if(!tr[p][s2[i]-'a'])
                tr[p][s2[i]-'a']=++cnt;
            p=tr[p][s2[i]-'a'];
        }
        end[p]=1;
        len[p]=_n;
    }
    queue<int>q;
    for(i=0;i<26;++i)
        if(tr[0][i])
            q.push(tr[0][i]);
    int u,v,r;
    while(!q.empty()){
        u=q.front();
        q.pop();
        for(i=0;i<26;++i){
            if((v=tr[u][i])){
                q.push(v);
                for(r=fail[u];r&&!tr[r][i];r=fail[r]);
                end[v]|=end[fail[v]=tr[r][i]];
            }
            else
                tr[u][i]=tr[fail[u]][i];
        }
    }
    for(p=0,i=1;i<=n;++i){
        stack[++top]=i;
        if(end[ins[i]=p=tr[p][s1[i]-'a']]){
            for(j=1;j<=len[p];++j)
                del[stack[top--]]=1;
            p=ins[stack[top]];
        }
    }
    for(i=1;i<=n;++i)
        if(!del[i])
            putchar(s1[i]);
    return 0;
}

思路:

AC自动机的Fail树有很多奇妙的性质.

例如串\(a\)是串\(b\)在Fail树上的祖先,那么\(a\)在\(b\)中应该出现\(dep[b]-dep[a]\)次.

(不过好像跟这题没什么关系)
 

把Alice的\(n\)个字符串插入AC自动机.

然后每插入一个修改串,都动态维护一下每个自动机中的节点,如果出现在修改串中,则该节点答案+1.

我们用修改串在自动机上走,每走到一个节点,我们都想要这个节点在Fail树上到根的路径上的答案均+1.

遗憾的是,这样有可能重复!

利用树链的并.

将所有要处理的节点按照dfs序排序,然后首先把它们到根的路径+1.

随后将相邻两个节点的LCA到根的路径-1.

非常科学.

怎么加?树链剖分?等TLE吧.

直接将标记累加在节点上,询问时就询问子树内的标记之和.

这样只需用树状数组维护DFS序即可.

可惜卡常数!

用倍增LCA会超时.

于是我们换用RMQlca,并用ZKW线段树维护.

估计ST表预处理也会超时.

反正总算还是水过去了.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
  
#define N 2002010
int ch[N][26],fail[N],ins[N],cnt;
char s[N];
  
int head[N],next[N],end[N];
inline void addedge(int a,int b){
    static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;
}
  
int in[N],out[N],dep[N],tclock;
void dfs(int x){
    in[x]=++tclock;
    for(int j=head[x];j;j=next[j])
        dep[end[j]]=dep[x]+1,dfs(end[j]);
    out[x]=tclock;
}
 
namespace Lca_system{
    int Seq[N<<1],a[8383608],M,ins[N],cnt;
    inline void build_dfs(int x){
        ins[x]=++cnt;
        Seq[cnt]=x;
        for(int j=head[x];j;j=next[j]){
            build_dfs(end[j]);
            Seq[++cnt]=x;
        }
    }
    inline int Min(int x,int y){
        if(x==-1||y==-1)return x==-1?y:x;
        return dep[x]<dep[y]?x:y;
    }
    inline void init(){
        build_dfs(0);
        for(M=1;M<cnt+2;M<<=1);
        memset(a,-1,sizeof a);
        for(int i=1;i<=cnt;++i)a[M+i]=Seq[i];
        for(int i=M-1;i>=1;--i)a[i]=Min(a[2*i],a[2*i+1]);
    }
    inline int ask(int tl,int tr){
        int re=-1;
        for(tl+=M-1,tr+=M+1;tl^tr^1;tl>>=1,tr>>=1){
            if(~tl&1)re=Min(re,a[tl^1]);
            if(tr&1)re=Min(re,a[tr^1]);
        }
        return re;
    }
    inline int lca(int x,int y){
        x=ins[x],y=ins[y];
        if(x>y)swap(x,y);
        return ask(x,y);
    }
}
 
int seq[N],num;
  
int A[N];
inline void modify(int x,int c){
    for(;x<=cnt+1;x+=x&-x)A[x]+=c;
}
inline int ask(int x){
    int re=0;for(;x;x-=x&-x)re+=A[x];return re;
}
  
inline bool cmp(const int&x,const int&y){return in[x]<in[y];}
  
inline int git(){
    int c,re;
    while(!isdigit(c=getchar()));
    re=c-'0';
    while(isdigit(c=getchar()))re=(re<<1)+(re<<3)+c-'0';
    return re;
}
char buf[100010*6],*o=buf;
inline void print(int x){
    static int s[100];int top=0;
    if(!x)*o++=48;else{for(;x;x/=10)s[++top]=x%10;for(int i=top;i>=1;--i)*o++=48+s[i];}
    *o++='\n';
}
int main(){
    int n=git();
    register int i,j;
      
    int len,p;
    for(i=1;i<=n;++i){
        scanf("%s",s);
        len=strlen(s),p=0;
        for(j=0;j<len;++j){
            if(!ch[p][s[j]-'a'])ch[p][s[j]-'a']=++cnt;
            p=ch[p][s[j]-'a'];
        }
        ins[i]=p;
    }
      
    queue<int>q;
    for(i=0;i<26;++i)if(ch[0][i])q.push(ch[0][i]);
    int u,v,r;
    while(!q.empty()){
        u=q.front(),q.pop();
        for(i=0;i<26;++i)if((v=ch[u][i])){
            q.push(v);
            for(r=fail[u];r&&!ch[r][i];r=fail[r]);
            fail[v]=ch[r][i];
        }
    }
      
    for(i=1;i<=cnt;++i)addedge(fail[i],i);
    dep[0]=1,dfs(0);
    Lca_system::init();
      
    int Q=git();
      
    int qte,x;
    while(Q--){
        qte=git();
        if(qte==1){
            scanf("%s",s);
            len=strlen(s),p=0,num=0;
            for(i=0;i<len;++i){
                while(p&&!ch[p][s[i]-'a'])p=fail[p];
                p=ch[p][s[i]-'a'];
                if(p)seq[++num]=p;
            }
            sort(seq+1,seq+num+1,cmp);
            for(i=1;i<=num;++i)modify(in[seq[i]],1);
            for(i=1;i<num;++i)modify(in[Lca_system::lca(seq[i],seq[i+1])],-1);
        }
        else{
            x=git();
            print(ask(out[ins[x]])-ask(in[ins[x]]-1));
        }
    }
      
    fwrite(buf,1,o-buf,stdout);
    return 0;
}

思路:

首先我的思路十分傻叉,是\(f[i][j][k]\)表示长度为\(i\),在自动机上的节点为\(j\),包含子串的状态为\(k\)可不可能.但这样复杂度直接爆炸.

但是我们可以令\(f[i][j]\)表示在自动机上的节点为\(i\),包含子串的状态为\(j\)时的最短长度.

这样我们就转化成了边权均为1的单源最短路,BFS就行了.

若按照字母字典序从小到大的顺序进行BFS,得出的就是字典序最小的答案了.

(有点卡内存)

(话说我一开始AC自动机都写错,没治了)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 12
#define L 610
 
short ch[L][26],end[L],pre[L],cnt;
 
char s[L];
 
int q[L],fr,ta;
short lastchar[L*(1<<N)];
int laststate[L*(1<<N)];
short state[L*(1<<N)];
short ins[L*(1<<N)];
bool vis[L][1<<N];
 
char ans[L];int id;
 
int main(){
    int n;scanf("%d",&n);register int i,j;
    int p,y;
    for(i=1;i<=n;++i){
        scanf("%s",s);int len=strlen(s);
        for(p=j=0;j<len;++j){
            if(!ch[p][y=s[j]-'A'])ch[p][y]=++cnt;p=ch[p][y];
        }end[p]|=1<<(i-1);
    }
    for(j=0;j<26;++j)if(ch[0][j])q[ta++]=ch[0][j];
    int u,v,r;
    while(fr^ta){
        u=q[fr++];
        for(j=0;j<26;++j)if(ch[u][j]){
            for(q[ta++]=v=ch[u][j],r=pre[u];r&&!ch[r][j];r=pre[r]);end[v]|=end[pre[v]=ch[r][j]];
        }
        else ch[u][j]=ch[pre[u]][j];
    }
    int mask;
    for(fr=ta=0,state[0]=ins[0]=0,++ta;fr^ta;){
        u=ins[fr],mask=state[fr];
        if(mask==(1<<n)-1){
            for(;fr;fr=laststate[fr])ans[++id]=lastchar[fr];
            for(i=id;i>=1;--i)putchar('A'+ans[i]);
            return 0;
        }
        for(j=0;j<26;++j)if(!vis[ch[u][j]][mask|end[ch[u][j]]]){
            lastchar[ta]=j,laststate[ta]=fr,ins[ta]=ch[u][j],state[ta]=mask|end[ch[u][j]];
            vis[ins[ta]][state[ta]]=1;
            ta++;
        }++fr;
    }
    return 0;
}