c173: 快速最長共同子字串
Tags : DP bit-vector 壓縮
Accepted rate : 9人/42人 ( 21% ) [非即時]
評分方式:
Tolerant

最近更新 : 2017-03-27 20:06

Content

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

Input

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

  • $1 \le |X|, |Y| \le 60000$
Output

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

Sample Input #1
TCA
GTA
TGGAC
TATCT
Sample Output #1
2
3
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (16%): 1.0s , <1K
公開 測資點#1 (16%): 1.0s , <1M
公開 測資點#2 (17%): 1.0s , <1M
公開 測資點#3 (17%): 1.0s , <1M
公開 測資點#4 (17%): 1.0s , <1M
公開 測資點#5 (17%): 1.0s , <1M
Hint :
  • 10000 組長度介於 1 到 100
  • 1000 組長度介於 200 到 500
  • 300 組長度介於 1000 到 2000
  • 50 組長度介於 2000 到 5000
  • 10 組長度介於 10000 到 60000
Tags:
DP bit-vector 壓縮
出處:
批改娘 [管理者:
morris1028 (碼畜)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」