好的,我将题目中的数字和名称用 ... 标出。
题目描述
有一个长度不超过 105 的字符串 S。
Farmer John 希望在 S 中删除 n 个屏蔽词(记为 t1,t2,…,tn),这些屏蔽词可能在 S 中出现多次。
FJ 的操作规则如下:
- 从 S 的开头开始寻找屏蔽词。
- 一旦找到任何一个屏蔽词,就删除它。
- 删除后,又重新从 S 的开头开始寻找(而不是接着往下找)。
- 重复这一过程,直到 S 中没有屏蔽词为止。
注意:删除一个单词后可能会导致 S 中出现另一个屏蔽词。
保证这 n 个屏蔽词中,不会出现一个单词是另一个单词的子串,这意味着每个屏蔽词在 S 中出现的开始位置是互不相同的(初始时不会重叠包含)。
输出最后的 S,并保证 S 不会变成空串。
输入格式
第一行包含字符串 S。
第二行包含整数 n。
接下来 n 行,每行一个字符串 ti。
输出格式
一行,输出操作后的 S。
数据范围
- 1≤∑∣ti∣≤105
- 1≤∣S∣≤105
- 所有字符串由小写字母组成
输入样例
begintheescapexecutionatthebreakofdawn
2
escape
execution
输出样例
beginthatthebreakofdawn
样例解释
母串:begintheescapexecutionatthebreakofdawn
屏蔽词:escape, execution
过程:
- 从头找,先找到 escape,删除它。
删除后得到 beginthexecutionatthebreakofdawn(实际直接拼接)。
- 重新从头找,此时 escape 已不存在,execution 出现在原位置但 e 被删了吗?原来 escapexecution 删除 escape 后剩下 execution,所以 execution 现在在 the 后面:begintheexecutionatthebreakofdawn。
- 再从头找,找到 execution,删除它。
删除后得到 begintheatthebreakofdawn,合并为 beginthatthebreakofdawn。
- 继续从头找,没有屏蔽词,结束。
最终输出:beginthatthebreakofdawn
这样题目就完整了,所有数字和名称都用 ... 标出。