【問題E20】：007情報員             [回前頁]

007情報員與008情報員，為了怕信件被偷看，所以兩個人定了暗號，在信裡面寫了兩大段字（小寫英文字母或者是數字且之間沒有空白），每一段字都只有一行。可是，只有這兩段字的「最長共同部份序列」才是所要表達的話。

所謂的「部份序列」是指對於一個字串，從其中挑出一些字元，每個挑出來的字要照原本的順序排列。例如：第一段字是abc0123那麼b02、abc123、b3、c、abc0123、ab12…都是這段字的「部份序列」。

「最長共同部份序列」：兩段字的所有部份序列中，取出相等的且長度最長的一組，即是它們的「最長共同部份序列」。

例一：

abcd0123

acdef2

這兩列的最長共同部份序列為：acd2，長度為4。

例二：

amvfeissyukou

mcwisopsytorupnb

這兩列的最長共同部份序列為：missyou，長度為7。

現在請你寫一個程式，可以找出兩列字串的最長共同部份序列的長度。

※    提示：

可以使用一個二維矩陣記錄處理的中間結果。也就是說可以使用d( i , j )來表示第一列字串前i個字元，及第二列字串前j個字元這兩個部份字串的最長共同部份序列的長度。

例如：

abcd0123

acdef2

則d(3,2)表示第一列的前3個字元abc與第二列的前2個字元ac的最長共同部份序列的長度，也就是2。

又如d(5,6)表示第一列的前5個字元abcd0及第二列的前6個字元的最長共同部份序列的長度，也就是3。當計算到矩陣的最後一項時就是兩字串的最長共同部份序列的長度了。

■    輸入檔說明

輸入檔中含有多組測試資料，每組測試資料均有二列文字資料，每列的資料均是由小寫英文字母及阿拉伯數字所組合成的(不會有其它符號或空格)，其長度必大於等於1且小於等於20。

當該組測試資料的第一列文字資料長度為1，且內容為0時，表示輸入檔結束，該筆資料及其後續所有資料均不需處理。

■    輸出檔說明

對每一組測試資料均輸出一列資料，該列只含一個整數，表示該組測試資料的最長共同部份序列的長度。(範圍是0到20)

■    範例輸入

■    範例輸出