回分類題庫
b033: 兩隻猴子
關鍵字: 動態規劃-最長共同子序列

測資點 : 5 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 672 Times / 577 Users | Submit : 1296 Times / 610 Users | Accepted rate : 95%
題目加入時間 : 2011-11-01 13:39

Content: 简体中文

有位教授看了「無限猴子定理」,想要印證它的真實性,於是找來兩隻猴子,希望牠們能打出莎士比亞的文學,可是猴子打出來的幾乎都是無法閱讀的文字。於是教授改變主意,打算分析這兩隻猴子打出來文字的相似性,他希望將兩隻猴子打出來的文字去掉一些字元之後,讓牠們打出來的內容是相同的,你能幫他找出兩隻猴子打出相同內容的最長長度是多少嗎?

Input:

輸入兩個只有大寫英文字母的字串(長度<=100),分別為兩隻猴子打出來的文字。

Output:

請輸出這兩段文字各自去掉某些字元使兩段文字相同,而這相同文字的最大長度為多少。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
輸入1:
ABCD ACBD

輸入2:
AFCBECCFBD FFEECDDAFB

Sample Output :

輸出1:
3

輸出2:
5

Hint :

Author :

動態規劃-最長共同子序列 (管理員:sagit)

  Solve it!   Status Forum