想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

46.2% (6/13)

Submission's AC Ratio

33.9% (21/62)



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.


如果一個字串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 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.


對於每一筆測資來說,首先會有一個正整數 n (1<=n<=50),代表 T集合的大小。然後會有一個字串S,接著 n個 T集合中的字串。

當你發現輸入 n=0的時候代表測試資料結束,請不要對這列做任何事情。

Output Format

For each test case, print a single integer indicating the minimum length resulting string possible.


Sample Input 1

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

Sample Output 1



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)


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