最長共同子序列定義如下:
給定兩序列 $S_1=\{x_1, x_2, x_3, x_4, \cdots\}$、$S_2=\{y_1, y_2, y_3, y_4, \cdots\}$,兩序列各自可分離出若干個子序列。若 $S_1 $ 存在一個子序列 $S_{1_{sub}} $ 並且 $S_2 $ 存在一個子序列 $S_{2_{sub}} $ 完全相等於 $S_{1_{sub}}$,則稱該子序列為兩序列 $S_1 $、$S_2 $ 的共同子序列。
其中子序列定義如下,若給定一序列 $Z=\{z_1, z_2, z_3, z_4, \cdots\}$,則可以找到一些序列 $Z_{sub} $ 滿足在不改變序列 $Z $ 元素順序的條件下刪除一些元素得到的新序列。
本題希望你可以寫出一個程式算出兩序列的最長共同子序列長度。
本題為多筆測資輸入。
每筆測資第一行輸入一字串代表序列 $S_1$,第二行輸入一字串代表序列 $S_2$。
兩序列均僅包含數字以及大寫英文字母,長度保證小於等於 $10^5$。
兩序列長度相乘結果必定小於等於 $10^8$。
輸出一整數代表兩序列的最長共同子序列長度並換行。
CORONAVIRUS WUHAN AAAAA SSSSS C8763 486 3678C 486
1 0 2 1
Ex. 序列 "RULE34" 的子序列有:
""
"R"、"U"、"L"、"E"、"3"、"4"
"RU"、"RL"、"RE"、"R3"、"R4"、"UL"、"UE"、"U3"、"U4"、"LE"、"L3"、"L4"、"E3"、"E4"、"34"
"RUL"、"RUE、"RU3"、"RU4"、"RLE"、"RL3"、"RL4"、"RE3"、"RE4"、"R34"、"ULE"、"UL3"、"UL4"、"UE3"、"UE4"、"U34"、"LE3"、"LE4"、"L34"、"E34"
"RULE"、"RUL3"、"RUL4"、"RUE3"、"RUE4"、"RU34"、"RLE3"、"RLE4"、"RL34"、"RE34"、"ULE3"、"ULE4"、"UL34"、"UE34"、"LE34"
"RULE3"、"RULE4"、"RUL34"、"RUE34"、"RLE34"、"ULE34"
"RULE34"
共 64 個。
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |