Наибольшая общая подпоследовательность

Наибольшая общая подпоследовательность (Longest Common Subsequence, LCS) — задача нахождения самой длинной последовательности символов, которая является подпоследовательностью обеих строк одновременно (символы не обязаны быть соседними).

Зачем нужно

LCS — фундаментальная задача, решаемая динамическим программированием за O(m·n). Она лежит в основе алгоритма diff (сравнение файлов), выравнивания биологических последовательностей и систем контроля версий. Понимание LCS необходимо для освоения широкого класса DP-задач на строках.

Где используется

  • Утилита diff (сравнение двух версий файла)
  • Git: вычисление изменений между коммитами
  • Биоинформатика: выравнивание ДНК и белковых последовательностей
  • Детектор плагиата: поиск общих фрагментов текста

Основной контент

Определение

Подпоследовательность — не обязательно непрерывная. Для строк ABCBDAB и BDCAB:

  • Одна из LCS: BCAB (длина 4)
  • Другая LCS: BDAB (длина 4)

Отличие от подстроки (substring): подстрока — непрерывна; подпоследовательность — нет.

Рекуррентное соотношение

dp[i][j] = длина LCS для s1[0..i-1] и s2[0..j-1]

Если s1[i-1] == s2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1

Иначе:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Реализация

function lcs(s1, s2) {
  const m = s1.length, n = s2.length;
  // dp[i][j]: LCS для s1[0..i-1] и s2[0..j-1]
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i-1] === s2[j-1]) {
        dp[i][j] = dp[i-1][j-1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
      }
    }
  }
  return dp[m][n];
}

console.log(lcs("ABCBDAB", "BDCAB")); // 4
console.log(lcs("AGGTAB", "GXTXAYB")); // 4 ("GTAB")

Восстановление самой подпоследовательности

function lcsString(s1, s2) {
  const m = s1.length, n = s2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++)
    for (let j = 1; j <= n; j++)
      dp[i][j] = s1[i-1] === s2[j-1]
        ? dp[i-1][j-1] + 1
        : Math.max(dp[i-1][j], dp[i][j-1]);

  // Backtracking
  let i = m, j = n, result = '';
  while (i > 0 && j > 0) {
    if (s1[i-1] === s2[j-1]) {
      result = s1[i-1] + result;
      i--; j--;
    } else if (dp[i-1][j] > dp[i][j-1]) {
      i--;
    } else {
      j--;
    }
  }
  return result;
}

console.log(lcsString("ABCBDAB", "BDCAB")); // "BCAB" или "BDAB"

Оптимизация памяти до O(n)

function lcsOpt(s1, s2) {
  const m = s1.length, n = s2.length;
  let prev = new Array(n + 1).fill(0);
  for (let i = 1; i <= m; i++) {
    const curr = new Array(n + 1).fill(0);
    for (let j = 1; j <= n; j++) {
      curr[j] = s1[i-1] === s2[j-1]
        ? prev[j-1] + 1
        : Math.max(prev[j], curr[j-1]);
    }
    prev = curr;
  }
  return prev[n];
}

Связанные задачи

  • Редакционное расстояние (Edit Distance): минимальное число операций для превращения одной строки в другую
  • Наибольшая возрастающая подпоследовательность (LIS): частный случай LCS с одной строкой
  • Shortest Common Supersequence: минимальная строка, содержащая оба как подпоследовательность

Частые ошибки

  • Путать подпоследовательность (subsequence) с подстрокой (substring) — задача совпадения подстрок решается иначе (скользящее окно или KMP).
  • Неверный базовый случай: dp[0][j] = dp[i][0] = 0 для всех i, j.
  • Перепутать направление backtracking — нужно идти от dp[m][n] к dp[0][0], а не наоборот.
  • Не учитывать, что LCS может быть не единственной.

Связанные темы

Ресурсы