TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的!雖然想像得出來也不一定可以就是了

User's AC Ratio

46.2% (6/13)

Submission's AC Ratio

33.9% (21/62)

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

1 ccdedefcde cde
3 aabaab aa ba ab
3 aabaab aa ba bb
0

Sample Output 1

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1900 65536 262144 1
1 1900 65536 262144 2