4528 - 提高:KMP算法: Censoring

通过次数

0

提交次数

5

时间限制 : 1 秒
内存限制 : 64 MB

原题来自:USACO 2015 Feb. Gold

有一个长度不超过 10^5的字符串S。Farmer John 希望在 S 中删掉 n 个屏蔽词(一个屏蔽词可能出现多次),这些词记为 t_1∼t_n

FJ 在 S 中从头开始寻找屏蔽词,一旦找到一个屏蔽词,FJ 就删除它,然后又从头开始寻找(而不是接着往下找)。FJ 会重复这一过程,直到 S 中没有屏蔽词为止。注意删除一个单词后可能会导致 S 中出现另一个屏蔽词。这 n 个屏蔽词不会出现一个单词是另一个单词子串的情况,这意味着每个屏蔽词在 S 中出现的开始位置是互不相同的,请帮助 FJ 完成这些操作并输出最后的 S。

输入

第一行包含一个字符串 S;

第二行包含一个整数 n;

接下来的 n 行,每行包含一个字符串,第 i 行的字符串是 t_i

输出

一行,输出操作后的 S。保证 S 不会变成空串。

样例

输入

begintheescapexecutionatthebreakofdawn
2
escape
execution

输出

beginthatthebreakofdawn

提示

数据范围:

对于全部数据,1≤∑∣t_i∣≤10^5,1≤∣S∣≤10^5 ,保证所有字符串只出现小写字母。