Azbuka

#include <bits/stdc++.h>

using namespace std;
// azbuka
const int MAX_N = 100010;
const int MAX_K = 102;
char s[MAX_N];
char p[MAX_K][MAX_K];

int nextState[MAX_K][26][MAX_K];
int currState[MAX_N][MAX_K];
int newState[MAX_K];
int prevPos[MAX_N];
int rem[MAX_N];
int len[MAX_K];
int endState[MAX_K];
void buildDFA(int k){
    for(int j = 0;j<k;++j){
        int n = strlen(p[j]);
        for(int i = 0;i<26;++i){
            nextState[j][i][0] = 0;
        }
        nextState[j][p[j][0]-'A'][0] = 1;
        int x = 0;
        for(int i = 1;i<n;++i){
            for(int c = 0;c<26;++c){
                nextState[j][c][i] = nextState[j][c][x];
            }
            nextState[j][p[j][i]-'A'][i] = i+1;
            x = nextState[j][p[j][i]-'A'][x];
        }
        endState[j] = x;
    }
}

int main(){
    scanf("%s", s);
    int k;
    scanf("%d", &k);
    for(int i = 0;i<k;++i){
        scanf("%s", p[i]);
        len[i] = strlen(p[i]);
    }
    buildDFA(k);
    int n = strlen(s);
    for(int i = 0;i<k;++i){
        currState[0][i] = 0;
    }
    for(int i = 0;i<=n;++i){
        prevPos[i] = i-1;
        rem[i] = 0;
    }
    for(int i = 1;i<=n;++i){
        for(int j = 0;j<k;++j){
            int c = s[i-1]-'A';
            newState[j] = nextState[j][c][currState[prevPos[i]][j]];
            currState[i][j] = newState[j];
            if(newState[j] == len[j]){
                /// match
                int st = i;
                for(int cnt = 0;cnt < len[j];++cnt){
                    st = prevPos[st];
                }
                rem[st+1]++;
                rem[i+1]--;
                prevPos[i+1] = st;
                break;
            }
        }
    }
    int curr = 0;
    for(int i = 1;i<=n;++i){
        curr += rem[i];
        if(!curr){
            printf("%c", s[i-1]);
        }
    }
    return 0;
}