分析

我们对于字串匹配，考虑 和 自动机。但是 对于删除操作不太好维护。所以我们考虑原串在 自动机上匹配。用栈保存路径，如果一旦发现该节点有一个标记，那么我们就往后退 步，之后继续匹配，直到原串匹配完毕，总的时间复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5e6 + 100;
int fail[N],ch[N][26],XZC[N],size,n;
char S[N],T[N],ans[N];
int top,son[N];
void insert(char *s) {
    int u = 0,len = strlen(s);
    for(int i = 0;i < len;i++) {
        int c = s[i] - 'a';
        if(!ch[u][c]) ch[u][c] = ++size;
        u = ch[u][c];
    }
    XZC[u] = max(XZC[u],len);
}
void build() {
    queue<int> q;
    for(int i = 0;i < 26;i++) if(ch[0][i]) q.push(ch[0][i]);
    while(!q.empty()) {
        int u = q.front();q.pop();
        for(int i = 0;i < 26;i++) {
            int v = ch[u][i];
            if(v) {
                fail[v] = ch[fail[u]][i];q.push(v);
                //f[v] |= f[ch[fail[u]][i]];
            }
            else ch[u][i] = ch[fail[u]][i];
        }
    }
    //for(int i = 1;i <= size;i++) cout << fail[i] << " " << f[i] << XZCl;
}
void match(char *s) {
    int u = 0;int len = strlen(s+1);
    for(int i = 1;i <= len;i++) {
        int c = s[i] - 'a';
        ans[++top] = s[i];son[top] = ch[u][c];
        if(ch[u][c]) u = ch[u][c];
        else u = 0;
        if(XZC[u]) {
            top -= XZC[u];
            u = son[top]; 
        }
    }
}
int main() {
    scanf("%s%d",S + 1,&n);
    for(int i = 1;i <= n;i++) {
        scanf("%s",T);insert(T);
    }
    build();
    match(S);
    for(int i = 1;i <= top;i++) printf("%c",ans[i]);
    return 0;
}