code:
```cpp
#include <algorithm>
#include <queue>
#include <cstdio>
#include <cstring>
#define MAXN 100005
#define MAXT 1000005
#define MAXS 27
using namespace std;
int m, root;
int fail[MAXT];
int trie[MAXT][MAXS];
int endf[MAXT];
void init() {
m = 1;
root = 1;
}
void insert(char *s) {
int np = root, len = 0;
for (int i = 0; s[i] != '\0'; ++i) {
++len;
int c = s[i] - 'a' + 1;
if (trie[np][c] == 0)
trie[np][c] = ++m;
np = trie[np][c];
}
endf[np] = len;
}
void get_fail() {
queue<int> q;
for (int i = 1; i <= 26; ++i) {
int y = trie[root][i];
if (y != 0) {
q.push(y);
fail[y] = root;
}
}
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = 1; i <= 26; ++i) {
int y = trie[x][i];
if (y != 0) {
fail[y] = trie[fail[x]][i];
q.push(y);
} else {
trie[x][i] = trie[fail[x]][i];
}
}
}
}
int main() {
init();
int n;
char *str = new char[MAXN];
scanf("%s", str);
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
char *s = new char[MAXN];
scanf("%s", s);
insert(s);
delete[] s;
}
get_fail();
int np = root, top = 0;
int *stack_string = new int[MAXN];
int *stack_position = new int[MAXN];
for (int i = 0; str[i] != '\0'; ++i) {
int c = str[i] - 'a' + 1;
if (trie[np][c] != 0)
np = trie[np][c];
else
np = root;
stack_position[++top] = np;
stack_string[top] = i;
if (endf[np] != 0) {
top -= endf[np];
if (top == 0)
np = root;
else
np = stack_position[top];
}
}
for (int i = 1; i <= top; ++i)
printf("%c", str[stack_string[i]]);
printf("\n");
delete[] str;
delete[] stack_position;
delete[] stack_string;
return 0;
}
```
by szTom @ 2020-06-27 15:45:53
@[szTom](/user/108422) 指针看不懂（wtcl
by laihaochen @ 2020-06-27 17:48:18