1059 - Censorship
Time Limit : 10 Second
Memory Limit : 128 MB
Submission: 94
Solved: 18
- Description
- As part of the new educational reform program, the CS department has decided to engage in censorship of
school texts. In this problem, you must help the department by writing a program which eliminates from
an input text string all occurrences of strings from a set of words to be filtered.
More formally, a word w can be removed from another string s if w is a substring of s (i.e., the char-
acters of w appear consecutively in s). Given a text string s and a set T of words to be filtered, return the
length of the shortest possible string that can result from iteratively removing words in T from s. Each word
in T may be removed from s an unlimited number of times.
- Input
- The input test file will contain multiple cases, with each case on a single line of input. Each test case begins
with a single integer n (where 1 ≤ n ≤ 50) indicating the size of the set T followed by a text string s to be
processed. Then, n strings t1 . . . tn indicating the words of T follow. The text string and all of the filter
words are guaranteed to contain only the characters ‘a’ through ‘z’ and will have lengths between 1 and 50.
All filter words will be unique. Input is terminated by a single line containing the number 0; do not process
this line.
- Output
- For each test case, print a single integer indicating the minimum length resulting string possible.
- sample input
-
1 ccdedefcde cde 3 aabaab aa ba ab 3 aabaab aa ba bb 0
- sample output
-
1 0 0
- hint
- Possible reductions giving the lengths shown for the three sample inputs are: ccdedefcde → cdefcde → fcde → f aabaab → baab → ab → ǫ aabaab → baab → bb → ǫ, where ǫ denotes the empty string.
- source
- Stanford Local 2007