How to solve LCS(Longest Common Subsequence) with a gap condition

Question

I know the general LCS problem and algorithm.

It's like this:

LCS(Xi, Yj) = [0 (i = 0 or j = 0)
           or LCS(Xi-1, Yj-1) + 1 (xi = yj)
           or max(LCS(Xi, Yj-1), LCS(Xi-1, Yj)) (xi != yj)]

But what if we add a gap condition?

For example:

String A is cttauaucagu
String B is cautauatcgu

if no gap condition
lcs = cauauagu

if gap = 1 (lcs gap is under 1)
lcs = auaua

if gap = 0 (lcs gap is under 0)
lcs = taua

Visual representation:

How do I solve this?

How do I make the DP Table?

Answer 1

The solution in this case is not much different. You will have to add another 2 parameters to the dp - the index of the last element included in the common subesequence from both strings. Then on each step of the dp only search for equal elements between the_last_included_element in the given string and the_last_included_elemement + gap + 1.