50003. Final Prob. 3: GLCS

I'm a slow walker, but I never walk backwards.

請看到題目敘述的最後一行,否則你可能會後悔。

我們在比較兩個字串,$A$和$B$,的相似程度時,可以用他們的最長共同子序列,也就是$LCS(A,B)$的長度來代表。

一個字串的子序列的是把它其中一些字元刪去所得到的新字串(可以不刪去任何字元,也可以刪去所有字元)。如果有一個字串$C$同時是$A,B$的子序列,我們稱$C$是$A,B$的「共同子序列」。兩字串的「最長共同子序列」即是它們所有的共同子序列中最長的一個。

但以$LCS$來代表字串的相似程度有個不完美之處:當子序列中相鄰的字元,在原本字串中間距太大時,意義會變得不大。例如,字串$A :adddddbdddcdde$和$B:abce$的最長共同子序列為$abce$,但這個最長共同子序列在$A$中相鄰字元的間距分別是$\lbrack 5,3,2]$,而通常我們覺得這樣的共同子序列沒辦法真實呈現兩個字串的相似性。

因此我們定義$GLCS$,也就是“有限間距最長共同子序列( Gapped Longest Common Subsequence )“。若$C$為$A$和$B$的共同子序列,且$C$在$A$與$B$中相鄰字元的間距皆不超過$K$,則$C$為一個$A$和$B$的有限間距共同子序列。$GLCS(A,B,K)$為$A$和$B$的有限間距共同子序列中,最長的一個。$GLCS$的長度比$LCS$的長度更能代表兩字串的相似程度。

舉例來說,若$A="acbdcaaaa"$,$B="addbcdbac"$,則當$K=2$時,一個符合條件的$GLCS$為$"abca"$。因為$"abca"$在$A$中相鄰字元的間隔為$\lbrack 1,1,0]$,間距皆不超過$2$( 在$A$中相鄰字元的間距也可以為$\lbrack 1,1,3]$,此時就出現了超過$2$的間距了,但只要有一種方法使相鄰字元的間距都不超過$K$就算符合條件 )。且$"abca"$在$B$中相鄰字元的間隔為$\lbrack 2,0,2]$,間距也皆不超過$2$。所以$GLCS(A,B,2)="abca"$,長度為$4$。

若將上例的$K$改為$1$,則$"abca"$就不符合條件了,因為$"abca"$在$B$中相鄰字元的間隔為$\lbrack 2,0,2]$,有超過$1$的間距。一個符合條件的$GLCS$為$"cda"$,因為$"cda"$在$A$中相鄰字元的間隔為$\lbrack 1,1]$,在$B$中相鄰字元的間隔為$\lbrack 0,1]$,間距皆不超過$1$。所以$GLCS(A,B,1)="cda"$,長度為$3$。

給定字串$A,B$與間距限制$K$,請求出$GLCS(A,B,K)$的長度。注意,在子任務中有$80\%$的分數滿足條件$K=max(length(A),length(B))$,這樣的條件下$GLCS$跟$LCS$是相同的。因此,如果你會寫一般的$LCS$,你至少可以在這題拿到 $20$分,請不要跳過。

Input/Output

第一行有一個正整數$T$,代表有幾組測試資料。( $T \leq 3$ )

每筆測試資料中:

第一行為一個正整數$K$,代表間距限制。

第二行為一個字串$A$,保證只由小寫英文字母組成。

第三行為一個字串$B$,保證只由小寫英文字母組成。

( $1 \leq length(A),length(B),K \leq 2000$ )

對於每一筆測試資料,請輸出一行,包含一個整數,代表$GLCS(A,B,K)$的長度。

Subtasks/Constraints

  1. $K=max(length(A),length(B))$,且$A,B$中只包含$a$一種字元 ( 5 pts )

  2. $K=max(length(A),length(B))$ ( 15 pts )

  3. $1 \leq length(A),length(B),K \leq 50$ ( 3 pts )

  4. 無特殊限制 ( 2 pts )

Sample Input

3
14
hahadsaggggqaq
hahadsasoeasy
13
dontbenervous
doyourbest
1
acbdaaaa
addbcdbac

Sample Output

8
5
3

說明:

$GLCS("hahadsaggggqaq","hahadsasoeasy",14)="hahadsaa"$,長度為$8$

$GLCS("dontbenervous","doyourbest",13)="dobes" or "doous"$,長度為$5$

$GLCS(A,B,1)="cda"$,長度為$3$

Discussion