https://www.luogu.com.cn/problem/P3121
卡时间，需要 trie 图优化

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e5 + 10;

char str[N];
int n;
char s[N];
int trie[N][26], tot, nxt[N], q[N], f[N];
int st[N], top;
int len[N];

void insert() {
    int p = 0, cnt = 0;
    for(int i = 1; s[i]; i++) {
        cnt++;
        int t = s[i] - 'a';
        if(trie[p][t] == 0) trie[p][t] = ++tot;
        p = trie[p][t];
    }
    len[p] = cnt;
}

void ACAM() {
    int hh = 0, tt = -1;
    for(int t = 0; t < 26; t++)
        if(trie[0][t]) q[++tt] = trie[0][t];
    while(hh <= tt) {
        int p = q[hh++];
        for(int t = 0; t < 26; t++) {
            int i = trie[p][t];
            if(i == 0) trie[p][t] = trie[nxt[p]][t];
            else {
                nxt[i] = trie[nxt[p]][t];
                q[++tt] = i;
            }
        }
    }
}

int main() {
    scanf("%s", str + 1);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        scanf("%s", s + 1);
        insert();
    }
    ACAM();

    st[++top] = 0;
    for(int i = 1, j = 0; str[i]; i++) {
        st[++top] = i;
        int t = str[i] - 'a';
        j = trie[j][t];
        f[i] = j;
        top -= len[j];
        j = f[st[top]];
    }

    for(int i = 2; i <= top; i++)
        printf("%c", str[st[i]]);
    return 0;
}