c173: 快速最長共同子字串
標籤 : DP bit-vector 壓縮
通過比率 : 25% (3 人 / 12 人 ) (非即時)
評分方式: Tolerant , 記憶體限制: 64 MB
最近更新 : 2017-03-27 20:06

內容 :

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

輸入說明

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

  • $1 \le |X|, |Y| \le 60000$
輸出說明

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

範例輸入
TCA
GTA
TGGAC
TATCT
範例輸出
2
3
測資資訊:
公開 測資點#0 (0%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
公開 測資點#5 (20%): 1.0s , <1M
提示 :
  • 10000 組長度介於 1 到 100
  • 1000 組長度介於 200 到 500
  • 300 組長度介於 1000 到 2000
  • 50 組長度介於 2000 到 5000
  • 10 組長度介於 10000 到 60000
標籤:
DP bit-vector 壓縮
出處:
批改娘 [編輯: morris1028 (碼畜) ]
編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」