A901.Censoring Gold--Gold

省选/NOI-

USACO

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

Farmer John has purchased a subscription to Good Hooveskeeping magazine for
his cows, so they have plenty of material to read while waiting around in the
barn during milking sessions. Unfortunately, the latest issue contains a
rather inappropriate article on how to cook the perfect steak, which FJ would
rather his cows not see (clearly, the magazine is in need of better editorial
oversight).
FJ has taken all of the text from the magazine to create the string S of
length at most 10^5 characters. He has a list of censored words t_1 ... t_N
that he wishes to delete from S. To do so Farmer John finds the earliest
occurrence of a censored word in S (having the earliest start index) and
removes that instance of the word from S. He then repeats the process again,
deleting the earliest occurrence of a censored word from S, repeating until
there are no more occurrences of censored words in S. Note that the deletion
of one censored word might create a new occurrence of a censored word that
didn't exist before.
Farmer John notes that the censored words have the property that no censored
word appears as a substring of another censored word. In particular this means
the censored word with earliest index in S is uniquely defined.
Please help FJ determine the final contents of S after censoring is complete.

输入格式

The first line will contain S. The second line will contain N, the number of
censored words. The next N lines contain the strings t_1 ... t_N. Each string
will contain lower-case alphabet characters (in the range a..z), and the
combined lengths of all these strings will be at most 10^5.

输出格式

The string S after all deletions are complete. It is guaranteed that S will
not become empty during the deletion process.

输入输出样例

  • 输入#1

    begintheescapexecutionatthebreakofdawn
    2
    escape
    execution
    

    输出#1

    beginthatthebreakofdawn
    
首页