#kMPybttg020206. 1470:Censoring

1470:Censoring

好的,这是整理好的题面,格式清晰。


题目描述

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

FJ 使用如下规则操作:

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

注意:删除一个单词后可能会导致 ( S ) 中出现另一个屏蔽词。
题目保证这 ( n ) 个屏蔽词中,不会出现一个单词是另一个单词子串的情况,这意味着每个屏蔽词在 ( S ) 中出现的开始位置是互不相同的(但同一屏蔽词多次出现的开始位置可能相同吗?不会,因为删除后会改变字符串,但保证初始时它们不会互相包含,所以每个屏蔽词在 ( S ) 中出现的开始位置是不同的)。

你需要帮助 FJ 完成这些操作,并输出最后的 ( S )。
保证最后 ( S ) 不会变成空串。


输入格式

第一行包含字符串 ( S )。
第二行包含整数 ( n )。
接下来的 ( n ) 行,每行一个字符串 ( t_i )。

输出格式

输出一行,表示操作后的 ( S )。


数据范围

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

输入样例

begintheescapexecutionatthebreakofdawn
2
escape
execution

输出样例

beginthatthebreakofdawn

样例解释

原始 ( S ):begintheescapexecutionatthebreakofdawn
屏蔽词:escape, execution

过程:

  1. 从头开始找屏蔽词:先找到 escape(在位置 begin 后面),删除它。
    删除后字符串变成:beginthe xecutionatthebreakofdawn(这里为了清晰,删除部分用空格表示,实际是直接拼接)。
  2. 重新从头开始找屏蔽词:发现 execution 不存在(因为现在开头是 beginthe xecution...),escape 也不存在。
  3. 但删除 escape 后,原来 execution 被拆开了吗?其实 execution 原来是从 e 开始,现在变成 xecution 开头,所以不是 execution 了。

等一下,检查原字符串:
原串 begintheescapexecutionatthebreakofdawn 中,escape 是从第 9 个字符(e)开始,execution 从第 15 个字符(e)开始,两者不重叠,所以删除 escape 后,execution 仍然完整。
executionescape 后面,删除 escape 后,字符串变为 beginthe xecutionatthebreakofdawn(删除了 9~14 位置共 6 个字符 escape,剩下的 execution 变成从原来第 9 个字符位置开始)。但此时 execution 在新字符串中的位置是否还在?
原字符串 escapexecution → 删除 escape 后剩下 executionexecution 在新字符串中成了开头是 execution 吗?不,原来是 escapexecution,删掉 escape 后得到 executionexecution 现在在新字符串中紧跟在 the 后面,即 begintheexecutionatthebreakofdawn
再从头找屏蔽词,找到 execution,删除它。
删除 execution 后得到 beginthe atthebreakofdawn,再合并为 beginthatthebreakofdawn

所以最终结果 beginthatthebreakofdawn


输出:

beginthatthebreakofdawn

这样题目就完整了,包括题意、输入输出格式、数据范围、样例及解释。