a342. Q-6-8. Local alignment - 彰化精誠中學

內容

輸入兩字串，計算local alignment的最大分數。評分機制為：兩字母相同得8分，相異-5分，字母與空白對應-3分。

輸入說明

第一行與第二行個有一個字串，字串均只由 ATCG 四個字母組成長度不
超過 500 。

輸出說明

Local alignment的最大分數。

範例輸入 #1

ATATCTTAACTGG
CGCGGATCATAA

範例輸出 #1

範例輸入 #2

AAAACTGAGGG
GGCTATT

範例輸出 #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

提示：

計算global alignment與LCS很類似，計算local alignment與global的差別在於：可以”昨日種種譬如昨日死”，DP過程中，如果前面的分數不好，可以放棄繼承，此外，最大分數未必出現在最後的位置。

標籤:

出處:

AP325 [管理者：

haha (大學長)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」