d074. Q-6-8. Local alignment - TCFSH CIRC Judge

Content

Alignment 是生物序列（如 DNA 與蛋白質）分析的重要問題，輸入兩個字元序列，我們要將兩序列的字母依照原順序做一個對應，過程中可以將任一序列的某些位置加入空白，

以輸入"$CTTAACT$"與"$CGGATCAT$"為例，以下是一個可能的 alignment（以-表示空白）：

$CTTAAC-T$

$CGGATCAT$

以下也是一個 alignment：

$C---TTAACT$

$CGGATCA--T$

alignment 的目的是要評估兩序列有多相似，我們會有一個評分機制，以下是一個例子：兩字母相同得 $8$ 分，相異 $-5$ 分，字母與空白對應 $-3$ 分。

給定評分機制，輸入兩序列，要計算最大的 alignment 分數。

Alignment 可分為 global alignment 與 local alignment，前者是輸入的序列整個要納入 alignment，而後者是兩序列各選取連續的一段（長度可為 $0$ ）來做 alignment。

輸入兩字串，計算 local alignment 的最大分數。

Input

第一行與第二行個有一個字串，

字串均只由 $ATCG$ 四個字母組成，

長度不超過 $500$。

Output

Local alignment 的最大分數。

Sample Input #1

ATATCTTAACTGG
CGCGGATCATAA

Sample Output #1

Sample Input #2

AAAACTGAGGG
GGCTATT

Sample Output #2

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (20%): 1.0s , <1K
公開測資點#1 (20%): 1.0s , <1K
公開測資點#2 (20%): 1.0s , <1K
公開測資點#3 (20%): 1.0s , <1K
公開測資點#4 (20%): 1.0s , <1K

Hint ：

Tags:

出處:

AP325 [管理者：

TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)

]

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