Gym102174B 炼金术（AC自动机）

有很多模式串，请求构造一个长度为n的串，使得给定的串不是构造串的子串。

如何判断是否为子串，可以考虑建立ac自动机，这样在跑ac自动机的时候就知道是否构造出现子串情况。

在构造的时候，我们最希望的就是遇到环，这样只要循环走就行。

因此我们考虑记忆化预处理从每个点能走的最长距离，如果遇到环直接将长度置为n+1

这样构造，就是往合法的情况走，因为已经预处理了，所以很好判断。

因为记忆化搜索，所以每个点只会走一次，把经过的点标记一下，如果遇到了经过的点，那么说明成为环

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10;
struct node{
    int cnt;
    node * nxt[27];
    node * fail;
    vector<node *> num;
}*rt;
node pool[N];
int n,m,idx;
int val[N];
int num;
int f[N];
void insert(string s){
    node *p=rt;
    int i;
    for(i=0;i<s.size();i++){
        int sign=s[i]-'a';
        if(p->nxt[sign]==NULL){
            p->nxt[sign]=pool+(++idx);
            p->nxt[sign]->cnt=++num;
        }
        p=p->nxt[sign];
        if(i==(int)s.size()-1){
            val[p->cnt]=1;
        }
    }
}
void build(){
    int i;
    queue<node *> q;
    rt->fail=rt;
    for(i=0;i<26;i++){
        if(rt->nxt[i]){
            rt->nxt[i]->fail=rt;
            rt->num.push_back(rt->nxt[i]);
            q.push(rt->nxt[i]);
        }
        else{
            rt->nxt[i]=rt;
            rt->nxt[i]->fail=rt;
        }
    }
    while(q.size()){
        auto t=q.front();
        q.pop();
        for(i=0;i<26;i++){
            if(t->nxt[i]){
                t->nxt[i]->fail=t->fail->nxt[i];
                t->fail->nxt[i]->num.push_back(t->nxt[i]);
                q.push(t->nxt[i]);
            }
            else{
                t->nxt[i]=t->fail->nxt[i];
            }
        }
        val[t->cnt]|=val[t->fail->cnt];
    }
}
int st[N];
int dfs(int u,node *p){
    if(f[u]!=-1)
        return f[u];
    f[u]=0;
    st[u]=1;
    for(int i=0;i<26;i++){
        if(!val[p->nxt[i]->cnt]){
            if(!st[p->nxt[i]->cnt])
            f[u]=max(f[u],dfs(p->nxt[i]->cnt,p->nxt[i])+1);
            else
            f[u]=n+1;
        }
    }
    st[u]=0;
    return f[u];
}
int main(){
    //ios::sync_with_stdio(false);
    memset(f,-1,sizeof f);
    rt=pool;
    rt->cnt=0;
    int i,j;
    cin>>n>>m;
    for(i=1;i<=m;i++){
        string s;
        cin>>s;
        insert(s);
    }
    build();
    dfs(0,rt);
    int cnt=n;
    node *p=rt;
    for(i=0;i<n;i++){
        cnt--;
        for(j=0;j<26;j++){
            if(f[p->nxt[j]->cnt]>=cnt){
                putchar('a'+j);
                p=p->nxt[j];
                break;
            }
        }
    }
    cout<<endl;
}