题解

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int trie[N][26],tot=1,vis[N],nxt[N],deep[N];
int n;
char S[N],T[N];
char st[N];
int top;
int num[N];
queue<int> q;
void built()
{
    int len=strlen(T);
    int u=1;        
    deep[1]=0; 
    for(int i=0;i<len;i++)
    {
        int v=T[i]-'a';
        if(trie[u][v]==0){trie[u][v]=++tot;deep[tot]=deep[u]+1;}
        u=trie[u][v];   
    } 
    vis[u]=1;  
}
void bfs()
{      
    for(int i=0;i<=25;i++)
    {
        int v=trie[1][i];
        if(v) nxt[v]=1,q.push(v);
        else trie[1][i]=1;     
    } 
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<=25;i++)   
        {
            int v=trie[u][i];
            if(v==0)    trie[u][i]=trie[nxt[u]][i];    
            else
            {
                q.push(v);
                nxt[v]=trie[nxt[u]][i];        
            }
        }
    }
}
void find()
{
    int u=1,ans=0;
    int len=strlen(S);
    for(int i=0;i<len;i++)
    {
        int v=S[i]-'a';
        u=trie[u][v];                      
        st[++top]=S[i];             
        num[top]=u;
        if(vis[u]==1)          
        {
            top-=deep[u];
            if(top==0) u=1;    
            else u=num[top];
        }
    }
    for(int i=1;i<=top;i++)
        cout<<st[i];
    cout<<endl;
      
}
int main()
{
    cin>>S;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>T;
        built();
    }
    bfs();
    find();
    return 0;
}

内存最优