题目描述
原题来自：USACO 2015 Feb. Gold
有一个长度不超过
10^5
105 的字符串
S
S。Farmer John 希望在
S
S 中删掉
n
n 个屏蔽词（一个屏蔽词可能出现多次），这些词记为
t_1\sim t_n
t1
∼tn
。
FJ 在
S
S 中从头开始寻找屏蔽词，一旦找到一个屏蔽词，FJ 就删除它，然后又从头开始寻找（而不是接着往下找）。FJ 会重复这一过程，直到
S
S 中没有屏蔽词为止。注意删除一个单词后可能会导致
S
S 中出现另一个屏蔽词。这
n
n 个屏蔽词不会出现一个单词是另一个单词子串的情况，这意味着每个屏蔽词在
S
S 中出现的开始位置是互不相同的，请帮助 FJ 完成这些操作并输出最后的
S
S。
输入
第一行包含一个字符串
S
S；
第二行包含一个整数
n
n；
接下来的
n
n 行，每行包含一个字符串，第
i
i 行的字符串是
t_i
ti
。
输出
一行，输出操作后的
S
S。保证
S
S 不会变成空串。
样例输入
begintheescapexecutionatthebreakofdawn
2
escape
execution
样例输出
beginthatthebreakofdawn
提示
数据范围与提示
对于全部数据，
1\le \sum |t_i|\le 10^5,1\le |S|\le 10^5
1≤∑∣ti
∣≤105,1≤∣S∣≤105，保证所有字符串只出现小写字母。
来源/分类
ybttg AC自动机