#aCybttg020403. 1481:Censoring

1481:Censoring

好的,我将题目中的数字和名称用 ...... 标出。


题目描述

有一个长度不超过 10510^5 的字符串 SS
Farmer John 希望在 SS 中删除 nn 个屏蔽词(记为 t1,t2,,tnt_1, t_2, \dots, t_n),这些屏蔽词可能在 SS 中出现多次。

FJ 的操作规则如下:

  1. SS开头开始寻找屏蔽词。
  2. 一旦找到任何一个屏蔽词,就删除它。
  3. 删除后,又重新从 SS 的开头开始寻找(而不是接着往下找)。
  4. 重复这一过程,直到 SS 中没有屏蔽词为止。

注意:删除一个单词后可能会导致 SS 中出现另一个屏蔽词。
保证这 nn 个屏蔽词中,不会出现一个单词是另一个单词的子串,这意味着每个屏蔽词在 SS 中出现的开始位置是互不相同的(初始时不会重叠包含)。

输出最后的 SS,并保证 SS 不会变成空串。


输入格式

第一行包含字符串 SS
第二行包含整数 nn
接下来 nn 行,每行一个字符串 tit_i

输出格式

一行,输出操作后的 SS


数据范围

  • 1ti1051 \le \sum |t_i| \le 10^5
  • 1S1051 \le |S| \le 10^5
  • 所有字符串由小写字母组成

输入样例

begintheescapexecutionatthebreakofdawn
2
escape
execution

输出样例

beginthatthebreakofdawn

样例解释

母串:begintheescapexecutionatthebreakofdawnbegintheescapexecutionatthebreakofdawn
屏蔽词:escapeescape, executionexecution

过程:

  1. 从头找,先找到 escapeescape,删除它。
    删除后得到 beginthexecutionatthebreakofdawnbeginthe xecutionatthebreakofdawn(实际直接拼接)。
  2. 重新从头找,此时 escapeescape 已不存在,executionexecution 出现在原位置但 ee 被删了吗?原来 escapexecutionescapexecution 删除 escapeescape 后剩下 executionexecution,所以 executionexecution 现在在 thethe 后面:begintheexecutionatthebreakofdawnbegintheexecutionatthebreakofdawn
  3. 再从头找,找到 executionexecution,删除它。
    删除后得到 begintheatthebreakofdawnbeginthe at thebreakofdawn,合并为 beginthatthebreakofdawnbeginthatthebreakofdawn
  4. 继续从头找,没有屏蔽词,结束。

最终输出:beginthatthebreakofdawnbeginthatthebreakofdawn


这样题目就完整了,所有数字和名称都用 ...... 标出。