背景

有限間距最長共同子序列 (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$ 時：

$$\begin{gathered} S=\text{ACBDCAA} \\ T=\text{ADDBCDBAC} \end{gathered}$$

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

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

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

題目描述

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