Как решить LCS(Longest Common Subsequence) с условием пропуска

Question

Я знаю общую проблему LCS и алгоритм.

Это вот так:

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)]

Но что, если мы добавим условие разрыва?

Например:

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

Визуальное представление:

Как мне это решить?

Как мне составить таблицу DP?

Answer 1

Решение в этом случае не сильно отличается. Вам нужно будет добавить еще 2 параметра в dp - индекс последнего элемента, включенного в общую подпоследовательность из обеих строк. Затем на каждом шаге dp ищите только одинаковые элементы между the_last_included_element в данной строке и the_last_included_elemement + gap + 1.