gym102174 B 炼金术

水深无声 2022-02-13 04:06 173阅读 0赞

#include <bits/stdc++.h>
    #define N 400005
    using namespace std;
    
    int tr[N][26],cnt=1;
    int e[N];
    int fail[N],v[N];
    int dp[N];
    
    void ins(char * s){
        int p=1;
        for(int i=0;s[i];i++){
            int k=s[i]-'a';
            if(!tr[p][k]){
                tr[p][k]=++cnt;
            }
            p=tr[p][k];
        }
        v[p]=1;
    }
    
    void build(){
        queue<int>q;
        memset(fail,0,sizeof(fail));
        for(int i=0;i<26;i++)tr[0][i]=1;
        q.push(1);
        while(!q.empty()){
            int k=q.front();q.pop();
            for(int i=0;i<26;i++){
                if(tr[k][i]){
                    fail[tr[k][i]]=tr[fail[k]][i];
                    v[tr[k][i]]|=v[fail[tr[k][i]]];
                    q.push(tr[k][i]);
                }
                else tr[k][i]=tr[fail[k]][i];
            }
        }
    }
    
    bool inq[N];
    int n,m;
    
    int dfs(int x){
        if(dp[x]!=-1) return dp[x];
        dp[x]=0;
        inq[x]=1;
        for(int i=0;i<26;i++){
            if(!v[tr[x][i]]){
                if(!inq[tr[x][i]]){
                    dp[x]=max(dp[x],dfs(tr[x][i])+1);
                }else{
                    return dp[x]=n+1;
                }
            }
        }
        inq[x]=0;
        return dp[x];
    }
    
    char s[N];
    
    int main(){
        memset(dp,-1,sizeof dp);
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            scanf("%s",s);
            ins(s);
        }
        build();
        dfs(1);
        int k=1;
        int nn=n;
        for(int i=1;i<=nn;i++){
            n--;
            for(int j=0;j<26;j++){
                if(!v[tr[k][j]]&&dp[tr[k][j]]>=n){
                    putchar('a'+j);
                    k=tr[k][j];
                    break;
                }
            }
        }
    }

ac自动机好题 首先要学会ac自动机类似于并查集路径压缩的写法 保证trie树上每个节点的儿子都不空 然后dfs在trie图上跑最长路 或者找到环