南外Day2-AC自动机

2023年8月2日陈麒润

T1

板子

#include<bits/stdc++.h>
#define MX 5200005
using namespace std;
int n,m,cnt;string s;
int t[MX][29],g[MX],fail[MX];
int o(char oo){return int(oo-&#039;a&#039;+1);}
void add(string str){
    int p=0;
    for(auto i:str){
        if(!t[p][o(i)]) t[p][o(i)]=++cnt;
        p=t[p][o(i)];
    }
    g[p]++;
}
void create(){
    queue<int> q;
    for(int i=1;i<=26;i++){
        if(t[0][i])
            q.push(t[0][i]);
    }
    while(q.size()){
        int u=q.front();q.pop();
        for(int i=1;i<=26;i++){
            if(t[u][i]){fail[t[u][i]]=t[fail[u]][i];q.push(t[u][i]);}
            else{t[u][i]=t[fail[u]][i];}
        }
    }
}
int gt(string str){
    int p=0,ans=0;
    for(auto i:str){
        p=t[p][o(i)];
        //cout<<p<<endl;
        int o=p;
        while(o){
            ans+=g[o];
            g[o]=0;o=fail[o];
        }
    }
    return ans;
}
signed main(){
    cin.tie(0);cout.tie(0);cin>>n;
    for(int opao=1;opao<=n;opao++){
        cin>>s;
        add(s);
    }
    create(); 
    cin>>s;
    cout<<gt(s);
    return 0;
}

T2

是的我添加了DP
总方案-不符合条件的方案

#include<bits/stdc++.h>
#define MX 2000005
using namespace std;
int n,m,cnt,mod=10007,ans=1;string s;
int t[MX][29],g[MX],fail[MX],f[105][MX];
bool cant[MX];
int o(char oo){return int(oo-&#039;A&#039;+1);}
void add(string str){
    int p=0;
    for(auto i:str){
        if(!t[p][o(i)]) t[p][o(i)]=++cnt;
        p=t[p][o(i)];
    }
    cant[p]=1;
}
void create(){
    queue<int> q;
    for(int i=1;i<=26;i++){
        if(t[0][i])
            q.push(t[0][i]);
    }
    while(q.size()){
        int u=q.front();q.pop();
        for(int i=1;i<=26;i++){
            if(t[u][i]){fail[t[u][i]]=t[fail[u]][i];
                cant[t[u][i]]|=cant[fail[t[u][i]]];
                q.push(t[u][i]);
            }else{t[u][i]=t[fail[u]][i];}
        }
    }
}
signed main(){
    cin.tie(0);cout.tie(0);cin>>n>>m;
    for(int opao=1;opao<=n;opao++){
        cin>>s;
        add(s);
    }
    create();
    f[0][0]=1; 
    for(int i=1;i<=m;i++)
    for(int j=0;j<=cnt;j++)
    for(int k=1;k<=26;k++)
    if(!cant[t[j][k]]){
        f[i][t[j][k]]+=f[i-1][j];
        f[i][t[j][k]]%=mod;
    }
    for(int i=1;i<=m;i++) ans=(ans*26)%mod;
    for(int i=0;i<=cnt;i++){ans=(ans+mod-f[m][i])%mod;}
    cout<<ans;
    return 0;
}

T3

dp

#include<bits/stdc++.h>
#define MX 20005
using namespace std;
int n,m,cnt,mod=10007,ans=1;string s;
int t[MX][5],g[MX],fail[MX],f[1005][MX],can[MX];
int o(char oo){return int(oo-&#039;A&#039;+1);}
void add(string str){
    int p=0;
    for(auto i:str){
        if(!t[p][o(i)]) t[p][o(i)]=++cnt;
        p=t[p][o(i)];
    }
    can[p]++;
}
void create(){
    queue<int> q;
    for(int i=1;i<=3;i++){
        if(t[0][i])
            q.push(t[0][i]);
    }
    while(q.size()){
        int u=q.front();q.pop();
        for(int i=1;i<=3;i++){
            if(t[u][i]){fail[t[u][i]]=t[fail[u]][i];
                q.push(t[u][i]);
            }else{t[u][i]=t[fail[u]][i];}
        }
        can[u]+=can[fail[u]];
    }
}
signed main(){
    cin.tie(0);cout.tie(0);cin>>n>>m;
    for(int opao=1;opao<=n;opao++){
        cin>>s;
        add(s);
    }
    create();
    memset(f,-0x3f,sizeof(f));
    for(int i=0;i<=m;i++) f[i][0]=0;
    for(int i=1;i<=m;i++)
    for(int j=0;j<=cnt;j++)
    for(int k=1;k<=3;k++)
        f[i][t[j][k]]=max(f[i][t[j][k]],f[i-1][j]+can[t[j][k]]);
    for(int i=0;i<=cnt;i++) ans=max(ans,f[m][i]);
    cout<<ans;
    return 0;
}

T4

数组开小被薄纱，警钟撅烂

#include<bits/stdc++.h>
#define MX 605
#define GP pair<int,int>
#define MP make_pair
using namespace std;
int n,m,cnt,opp,ti;string s;
int t[MX*26][29],g[MX*26],fail[MX*26],can[MX*26],fa[MX*4200],ans[MX*4200];
bool f[MX*26][9000];
queue<GP> q;
int o(char oo){return int(oo-&#039;A&#039;+1);}
void add(string str,int tme){
    int p=0;
    for(auto i:str){
        if(!t[p][o(i)]) t[p][o(i)]=++cnt;
        p=t[p][o(i)];
    }
    can[p]|=(1<<(tme-1));
}
void create(){
    queue<int> qq;
    for(int i=1;i<=26;i++){
        if(t[0][i])
            qq.push(t[0][i]);
    }
    while(qq.size()){
        int u=qq.front();qq.pop();
        can[u]|=can[fail[u]];
        for(int i=1;i<=26;i++){
            if(t[u][i]){fail[t[u][i]]=t[fail[u]][i];
                qq.push(t[u][i]);
            }else{t[u][i]=t[fail[u]][i];}
        }
    }
}
signed main(){
    cin.tie(0);cout.tie(0);cin>>n;
    for(int opao=1;opao<=n;opao++){
        cin>>s;
        add(s,opao);
    }
    create();
    q.push(MP(0,0));f[0][0]=1;
    //cout<<"AC Automaton wants to kill cqr\n";
    while(1){
        GP top=q.front();q.pop();
        int p=top.first,st=top.second;
        if(st+1==(1<<n)){
            s="";
            while(ti){
                s=char(ans[ti]+&#039;A&#039;-1)+s;
                ti=fa[ti];
            }
            cout<<s;
            return 0;
        }
        for(int i=1;i<=26;i++){
            int u=t[p][i];
            int v=st|can[u];
            if(!f[u][v]){
                f[u][v]=1;
                q.push(MP(u,v));
                fa[++opp]=ti;
                ans[opp]=i;
            }
        }
        ti++;
    }
    //cout<<"AC Automaton killed cqr";
    return 0;
}

T5

搜索，DP，AC自动机=毒瘤

#include<bits/stdc++.h>
#define MX 101
#define GP pair<int,int>
#define MP make_pair
#define int long long
using namespace std;
int n,m,cnt,opp,ti,ans;string s;
int t[MX][29],g[MX],fail[MX],can[MX],f[MX][MX][1200],at[30];
bool ck[MX][MX][1200],c2[MX][MX][1200];
queue<GP> q;
int o(char oo){return (int)(oo-&#039;a&#039;+1);}
void add(string str,int tme){
    int p=0;
    for(auto i:str){
        if(!t[p][o(i)]) t[p][o(i)]=++cnt;
        p=t[p][o(i)];
    }
    can[p]|=(1<<(tme-1));
}
void create(){
    queue<int> qq;
    for(int i=1;i<=26;i++){
        if(t[0][i])
            qq.push(t[0][i]);
    }
    while(qq.size()){
        int u=qq.front();qq.pop();
        can[u]|=can[fail[u]];
        for(int i=1;i<=26;i++){
            if(t[u][i]){fail[t[u][i]]=t[fail[u]][i];
                qq.push(t[u][i]);
            }else{t[u][i]=t[fail[u]][i];}
        }
    }
}
bool dfs1(int si,int sj,int sk){
    if(si>n){return ck[si][sj][sk]=(sk==opp);}
    if(c2[si][sj][sk]) return ck[si][sj][sk];
    c2[si][sj][sk]=1;bool flg=0;
    for(int i=1;i<=26;i++)
        flg|=dfs1(si+1,t[sj][i],sk|can[t[sj][i]]);
    return ck[si][sj][sk]=flg;
}
void dfs2(int si,int sj,int sk){
    if(!ck[si][sj][sk]){return;}
    if(si>n){
        for(int i=1;i<=n;i++)
            cout<<char(at[i]+&#039;a&#039;);
        cout<<&#039;\n&#039;;
        ans--;if(!ans){exit(0);}
        return;
    }
    for(int i=1;i<=26;i++){
        at[si]=i-1;
        dfs2(si+1,t[sj][i],sk|can[t[sj][i]]);
    }
}
signed main(){
    cin.tie(0);cout.tie(0);cin>>n>>m;
    for(int opao=1;opao<=m;opao++){
        cin>>s;
        add(s,opao);
    }
    create();opp=(1<<m)-1;
    q.push(MP(0,0));f[0][0][0]=1;
    //cout<<"AC Automaton wants to kill cqr\n";
    for(int i=1;i<=n;i++)
    for(int j=0;j<=cnt;j++)
    for(int k=0;k<=opp;k++)
    if(f[i-1][j][k])
    for(int l=1;l<=26;l++)
    f[i][t[j][l]][k|can[t[j][l]]]+=f[i-1][j][k];

    for(int i=0;i<=cnt;i++) ans+=f[n][i][opp];
    cout<<ans<<&#039;\n&#039;;if(ans>42) return 0;
    dfs1(1,0,0);dfs2(1,0,0);
    cout<<"AC Automaton killed cqr";
    return 0;
}

T6

训练日志