回分類題庫
d094: 2009 程式達人 H - 香腸的新鮮度問題
出處:

Difficulity : 2
Accepted : 17 Times | Submit :44 Times | Clicks : 1500
Accepted : 8 Users | Submit : 9 Users | Accepted rate : 89%
Time Limit :2001 ms | Memory Limit : 32001 KBytes
題目加入時間 : 2009-06-02 00:48

Content :

大仁研究所裡科學家發現,香腸的結構可以透過元素序列來表示,且有獨特的新鮮元素集合可以幫助分析香腸的新鮮度。透過這樣的檢驗機制,可以讓消費者買得放心、吃得安心。
這邊舉個簡單的例子來說,假設這個新鮮元素集合為

{A, AB, BA, CA, BBC}

要分析香腸的新鮮度,必須使用特殊的儀器將那條香腸中的元素序列讀取出來。機器會以大寫英文字母的方式列出元素的順序。舉今天早上才在菜市場購買的黑豬肉香腸為例,機器列出的元素序列為ABABACABAABEAB。

科學家從最前頭開始比對香腸的新鮮元素集合,因為香腸如果有變質不新鮮,會從序列的尾端開始產生變異。將整個序列切成若干個小段,每個小段都對應到新鮮元素集合當中的元素,直到沒辦法找到對應的元素為止,能夠對應的長度越長,香腸也就越新鮮。以剛剛的黑豬肉香腸為例,元素序列可以被切為

A-BA-BA-CA-BA-AB-EAB

的組合(注意此序列分析到EAB之前就無法繼續對應新鮮元素集合裡的元素),成功對應的序列長度為11,則我們可以得到此香腸的新鮮度為11。

因為對應香腸序列的排列方式可能有很多種,科學家定標準要以能夠對應的最長程度來當作新鮮度指標。這樣的分析對於消費者來說有點太困難了,請聰明的你們寫個程式來幫助消費者判斷香腸的新鮮度。

Input :

輸入資料的第一行開始表示的是新鮮元素集合,包括1~200個元素(長度為1~10不等)組成的集合,用空格分開每個元素,字母全部是大寫,資料可能不止一行,但集合中的元素不會重複。新鮮元素集合結束的標誌是只包含一個“.”的一行。接著是取出的香腸結構序列,長度為1~200,000不等,用一行或者多行的字串來表示,每行不超過76個字元。分行符號並不是其結構元素的一部分。

Output :

只有一行,輸出一個整數,表示所擷取到的香腸新鮮度。

Sample Input :

A AB BA
CA BBC
.
ABABACAB
AABC

Sample Output :

11

Hint :


  

Author :


  Solve it!   Status Forum (0)

C++
C
JAVA
37198. nothinglo (206 ms , 1756KB)
37197. MK (206 ms , 1768KB)
37196. MK (224 ms , 1756KB)
51297. uglyman (244 ms , 1766KB)
42702. king_of_laba (794 ms , 1770KB)
55499. ag100 (52 ms , 1456KB)
7295. yuhanlyu (84 ms , 1166KB)
55498. ag100 (86 ms , 1462KB)
7296. yuhanlyu (88 ms , 1560KB)
55500. ag100 (90 ms , 1474KB)
沒有解題記錄

執行時間會受很多因素影響因此僅供參考,主機等級請看這裡