a311. 基本演算法練習 - 最長連續共同子序列

內容

最長連續共同子序列定義如下：如有兩序列 $S_1$ 、 $S_2$ ，兩序列各自可分離出若干個連續子序列。若 $S_1$ 存在一個連續子序列 $S_{1_{sub}}$ 並且 $S_2$ 存在一個連續子序列 $S_{2_{sub}}$ 完全相等於 $S_{1_{sub}}$ ，則稱該連續子序列為兩序列 $S_1$ 、 $S_2$ 的共同連續子序列。

本題希望你可以寫出一個程式算出兩序列的最長連續共同子序列長度。

輸入說明

本題為多筆測資輸入。

每筆測資第一行輸入一字串代表序列 $S_1$ ，第二行輸入一字串代表序列 $S_2$ 。

兩序列均僅包含數字以及大寫英文字母，長度保證小於等於 $100000$ 。

輸出說明

輸出一整數代表兩序列的最長連續共同子序列長度並換行。

範例輸入

1RF0JRTST6
N0JRTDST61
SCHOOL
HAPPINESS
AAAAA
SSSSS

範例輸出

4
1
0

測資資訊：

記憶體限制： 16 MB
公開測資點#0 (11%): 1.0s , <1K
公開測資點#1 (11%): 1.0s , <1K
公開測資點#2 (11%): 1.0s , <1M
公開測資點#3 (11%): 2.0s , <1M
公開測資點#4 (11%): 2.0s , <1M
公開測資點#5 (11%): 2.0s , <1M
公開測資點#6 (11%): 2.0s , <1M
公開測資點#7 (11%): 1.0s , <1M
公開測資點#8 (12%): 1.0s , <1M

提示：

標籤:

Basic Algorithm DP Dynamic Programming

出處:

108學年度(下)復旦期末檢定考程式設計進階班 FDCS 8th 進階教學 [管理者：

fdhs108rex (RexWu)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」