回『原創/不分類題庫』
c173: 快速最長共同子字串
標籤 : DP bit-vector 壓縮

通過比率 : 29% (2 人 / 7 人 ) (非即時)
評分方式: Tolerant , 記憶體限制: 64 MB
公開 測資點 1 (0%): 1.0s , <1K
公開 測資點 2 (20%): 1.0s , <1M
公開 測資點 3 (20%): 1.0s , <1M
公開 測資點 4 (20%): 1.0s , <1M
公開 測資點 5 (20%): 1.0s , <1M
公開 測資點 6 (20%): 1.0s , <1M
最近更新 : 2017-03-27 20:06

內容 :

給兩個字串 $X, \; Y$,在兩個字串中都有出現且最長的子序列 (subsequence),意即最長共同子字串。

輸入說明 :

有多組測資,每組測資有兩行字串 $X, \; Y$,$X, \; Y$ 只由 A T C G 四個字母構成。

輸出說明 :

針對每一組測資,輸出一行 $X, \; Y$ 的最長共同子字串長度。

範例輸入 : help
若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
TCA
GTA
TGGAC
TATCT
範例輸出:
2
3
提示 :
  • 10000 組長度介於 1 到 100
  • 1000 組長度介於 200 到 500
  • 300 組長度介於 1000 到 2000
  • 50 組長度介於 2000 到 5000
  • 10 組長度介於 10000 到 60000
標籤:
DP bit-vector 壓縮
出處:
批改娘 (管理:morris1028)

本題狀況 本題討論 排行