Наибольшая Общая ПодпоследовательностьLongest Common Subsequence

Пусть dp[i][j] — длина LCS первых i символов строки A и первых j символов строки B. Если последние рассматриваемые символы совпадают (A[i-1] == B[j-1] в 0-индексации), их выгодно включить в общую подпоследовательность: dp[i][j] = dp[i-1][j-1] + 1 — расширяем LCS префиксов без этих двух символов на один общий символ. Если символы не совпадают, общий символ на этой паре позиций не образуется, и LCS первых i и j символов не может быть длиннее, чем LCS одного из двух более коротких префиксов: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) — либо отбрасываем последний символ A, либо последний символ B, и берём лучший вариант. Базовый случай: dp[0][j] = dp[i][0] = 0 (пустая строка не имеет общих символов ни с чем).Let dp[i][j] be the length of the LCS of the first i characters of A and the first j characters of B. If the last characters under consideration match (A[i-1] == B[j-1] with 0-indexing), it's always beneficial to include them in the common subsequence: dp[i][j] = dp[i-1][j-1] + 1 — extending the LCS of the prefixes without these two characters by one shared character. If they don't match, no shared character is formed at this pair of positions, and the LCS of the first i and j characters can't be longer than the LCS of one of the two shorter prefixes: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) — either drop A's last character or B's last character, and take the better option. The base case: dp[0][j] = dp[i][0] = 0 (an empty string shares nothing with anything).

Ответ на задачу — dp[n][m], где n = |A|, m = |B|. Чтобы восстановить саму подпоследовательность, а не только её длину, идут обратным проходом от dp[n][m]: если A[i-1] == B[j-1], этот символ входит в LCS — добавляем его в начало ответа и переходим по диагонали к dp[i-1][j-1]; иначе идём в сторону большего из dp[i-1][j] и dp[i][j-1] (при равенстве можно выбрать любое направление — оба ведут к LCS одинаковой длины, хотя, возможно, разной по составу).The answer to the problem is dp[n][m], where n = |A|, m = |B|. To reconstruct the actual subsequence, not just its length, trace backward from dp[n][m]: if A[i-1] == B[j-1], that character is part of the LCS — prepend it to the answer and move diagonally to dp[i-1][j-1]; otherwise move toward whichever of dp[i-1][j] and dp[i][j-1] is larger (on a tie, either direction can be taken — both lead to an LCS of the same length, though possibly a different composition).

int lcsLength(const std::string& a, const std::string& b) {
    int n = a.size(), m = b.size();
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (a[i-1] == b[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;      // совпадение — по диагонали// a match — diagonally
            else
                dp[i][j] = std::max(dp[i-1][j], dp[i][j-1]);
    return dp[n][m];
}

Две короткие строки — демонстрация проигрывает заполнение 2D-таблицы ячейка за ячейкой, слева направо, сверху вниз, а затем восстанавливает саму подпоследовательность обратным проходом от правого нижнего угла.Two short strings — the demo auto-plays filling the 2D table cell by cell, left to right, top to bottom, then reconstructs the actual subsequence with a backward pass from the bottom-right corner.