c173.
快速最長共同子字串
Tags
:
DP
bit-vector
壓縮
Accepted rate : 11人/65人 ( 17% ) [非即時]
評分方式：
最近更新 : 2017-03-27 20:06
Accepted rate : 11人/65人 ( 17% ) [非即時]
評分方式：
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
公開 測資點#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:
出處:
批改娘
[管理者：
morris1028
(碼畜)
]
| ID | User | Problem | Subject | Hit | Post Date |
|
沒有發現任何「解題報告」
|
|||||