背景

有限間距最長共同子序列 (Gapped Longest Common Subsequence, 簡稱 GLCS) 是一種 LCS 的變形，而 LCS 想必早已成了經典題型。

回顧一下最長共同子序列 LCS 的解法，可以利用最簡單的 $O(NM)$ 動態規劃完成或者在特殊不重複情況下轉化成 LIS 在 $O(N \log N)$ 時間完成，轉換成 LIS 是有風險的，有機會退化成 $O(NM \log N)$。說不定還有比 $O(NM)$ 更快的算法去計算 LCS。

GLCS 的特點在於挑選子序列時，挑選到的相鄰字符位置之間最多有 $K$ 個字符不選。可強迫挑選出的相似序列盡可能是有意義的。

例如兩個字符串 $S, \; T$ 要求 GLCS，當 $K = 2$ 時：

$$S = \text{ACBDCAA} \\ T = \text{ADDBCDBAC} $$

則 `ABCA` 是一組合法的 $K = 2$  時的 GLCS，挑選方案如下

    0123456789
S = ACBDCAA
    ^ ^ ^^
T = ADDBCDBAC
    ^  ^^  ^

    0123456789
S = ACBDCAA
     ^ ^ ^
T = ADDBCDBAC
        ^^ ^

題目描述

給予兩個字符串 $S, \; T$ 以及限制間距 $K$，求出 GLCS 的長度為何。