彭先生任職於證券公司，是一位股票分析師。公司經理認為目前的股票分析 軟體仍可再改進，希望彭先生再設計一套更準確的軟體。近日來，彭先生埋頭鑽 研，他發現過去的研究結果，有人提到，如果能在歷史資料中，找到與近期股票 走勢相近的樣型，即可使用此歷史樣型的交易策略，做為近期的買賣策略。為了 驗證這樣的講法是否正確，彭先生從股票歷史資料抽出一些特徵資料，並以大寫 英文字母 A~Z 代表特徵資料，因此股票資料變成一串的英文字母序列。判斷近 期股票資料與某一段歷史資料是否相近，就變成判斷二串字母序列(長度不一定 相等 ) 的相似度，亦即找出兩者的最長共同子序列 (LCS ， longest  common subsequence)。

在計算二串股票資料序列的相似度時，還有一個限制，兩個相似點(相同字 母)的前後間距不能太遠，否則相似度會被扭曲。發現了這個特性後，彭先生將 此問題正式定義為「有間距限制的最長共同子序列」 (GLCS,  gapped  longest common subsequence)問題。

假設第一個序列稱為a，第二個序列稱為β。例如，

a=“ACBDCAA”      β =“ADDBCDBAC” 。兩者在無間距限制的情形下，其  LCS  可為 “ADCA” ，“ABCA”，或“ACBC”，長度為 4。假設間距限制如下：

A 2, B 0, C 3, D 0

上述間距之意義為，如果字母 A 被選入 LCS 中，則與其前一個

被選入的字母之 間，在a序列最多只能有 2 個未被選入的字母，

在β序列亦同。a與β在上述間 距限制的情形，GLCS 可

為“ACA”或“ACC”，長度為 3。

        對於無間距限制的情形，可將每個字母的間距視為無限大。本題的答案只要 輸出 GLCS 的長度即可。