#P3121. [USACO15FEB] Censoring G

[USACO15FEB] Censoring G

题目描述

FJ 把杂志上所有的文章摘抄了下来并把它变成了一个长度不超过 10510^5 的字符串 ss。他有一个包含 nn 个单词的列表,列表里的 nn 个单词记为 t1tnt_1 \cdots t_n。他希望从 ss 中删除这些单词。

FJ 每次在 ss 中找到最早出现的列表中的单词(最早出现指该单词的开始位置最小),然后从 ss 中删除这个单词。他重复这个操作直到 ss 中没有列表里的单词为止。注意删除一个单词后可能会导致 ss 中出现另一个列表中的单词。

FJ 注意到列表中的单词不会出现一个单词是另一个单词子串的情况,这意味着每个列表中的单词在 ss 中出现的开始位置是互不相同的。

请帮助 FJ 完成这些操作并输出最后的 ss

输入格式

第一行是一个字符串,表示文章 ss

第二行有一个整数,表示单词列表的单词个数 nn

33 到第 (n+2)(n + 2) 行,每行一个字符串,第 (i+2)(i + 2) 行的字符串 tit_i 表示第 ii 个单词。

输出格式

输出一行一个字符串,表示操作结束后的 ss

begintheescapexecutionatthebreakofdawn 
2 
escape 
execution 

beginthatthebreakofdawn 

提示

数据规模与约定

对于全部的测试点,保证:

  • $1 \leq |s|, \sum\limits_{i = 1}^n |t_i|, n \leq 10^5$。
  • 字符串均只含小写字母。
  • 操作结束后 ss 不会被删成空串。
  • 对于所有的 iji \neq jtit_i 不是 tjt_j 的子串。

其中对于一个字符串 xx,约定 x|x| 表示 xx 的长度。


提示

操作过程中 ss 有可能某一个前缀子串被完全删除,请格外注意这一点。