1071 . [討論題] 字串消去問題(Censorship)
TopCoder
Tags
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 characters 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.
以下是爛爛的中文敘述(XDrz)：
如果一個字串W 是字串S 的子字串，那麼我們可以將W 從S中去除。
現在給你S以及一些可以合法進行消去動作的字串集合T (裡面包含許多允許的W)，請你判斷S經過一定順序的消去之後，最少能夠剩下多少字母？
Input Format
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.
以下仍是爛爛的中文敘述(逃:p)
輸入檔可能包含許多測試資料，每一筆測試資料佔一列。
對於每一筆測資來說，首先會有一個正整數 n (1<=n<=50)，代表 T集合的大小。然後會有一個字串S，接著 n個 T集合中的字串。
所有字串的長度都在1到50之間，並且只包含了小寫英文字母，字串間以一個空白格開。
當你發現輸入 n=0的時候代表測試資料結束，請不要對這列做任何事情。
Output Format
For each test case, print a single integer indicating the minimum length resulting string possible.
對於每一筆測試資料，請輸出一個整數：S字串經過消去之後最少得留下的字母個數。
Sample Input 1
3 aabaab aa ba ab
3 aabaab aa ba bb
0
Sample Output 1
0
0
Hints
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.
Problem Source
原TIOJ1071 / NTU Judge(problem 0068)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 50 |
| 2 | 1 | 50 |