#kMPybttg020206. 1470:Censoring
1470:Censoring
好的,这是整理好的题面,格式清晰。
题目描述
有一个长度不超过 ( 10^5 ) 的字符串 ( S )。
Farmer John 希望在 ( S ) 中删除 ( n ) 个屏蔽词(记为 ( t_1, t_2, \dots, t_n )),这些屏蔽词可能在 ( S ) 中出现多次。
FJ 使用如下规则操作:
- 从 ( S ) 的开头开始寻找屏蔽词。
- 一旦找到任何一个屏蔽词,就删除它。
- 删除后,又从 ( S ) 的开头开始寻找(而不是接着往下找)。
- 重复这一过程,直到 ( 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
过程:
- 从头开始找屏蔽词:先找到
escape(在位置begin后面),删除它。
删除后字符串变成:beginthe xecutionatthebreakofdawn(这里为了清晰,删除部分用空格表示,实际是直接拼接)。 - 重新从头开始找屏蔽词:发现
execution不存在(因为现在开头是beginthe xecution...),escape也不存在。 - 但删除
escape后,原来execution被拆开了吗?其实execution原来是从e开始,现在变成xecution开头,所以不是execution了。
等一下,检查原字符串:
原串 begintheescapexecutionatthebreakofdawn 中,escape 是从第 9 个字符(e)开始,execution 从第 15 个字符(e)开始,两者不重叠,所以删除 escape 后,execution 仍然完整。
但 execution 在 escape 后面,删除 escape 后,字符串变为 beginthe xecutionatthebreakofdawn(删除了 9~14 位置共 6 个字符 escape,剩下的 execution 变成从原来第 9 个字符位置开始)。但此时 execution 在新字符串中的位置是否还在?
原字符串 escapexecution → 删除 escape 后剩下 execution,execution 在新字符串中成了开头是 execution 吗?不,原来是 escapexecution,删掉 escape 后得到 execution,execution 现在在新字符串中紧跟在 the 后面,即 begintheexecutionatthebreakofdawn。
再从头找屏蔽词,找到 execution,删除它。
删除 execution 后得到 beginthe atthebreakofdawn,再合并为 beginthatthebreakofdawn。
所以最终结果 beginthatthebreakofdawn。
输出:
beginthatthebreakofdawn
这样题目就完整了,包括题意、输入输出格式、数据范围、样例及解释。