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

Longest Common Subsequence: найти максимальную длину подпоследовательности, общей для двух строк. DP таблица [m+1][n+1], сложность O(mn). Применение: diff, биоинформатика, контроль версий.

📖6 мин чтения📊Уровень 7🗺️6 подтем📅16 апреля 2026 г.

Автор: Бессмертный А.П.

Загрузка карты...

Алгоритм LCS
Longest Common Subsequence: наибольшая общая подпоследовательность строк X и Y. DP таблица dp[i][j]: LCS для X[1..i] и Y[1..j]. Если X[i]=Y[j]: dp[i][j] = dp[i-1][j-1]+1, иначе max(dp[i-1][j], dp[i][j-1]). O(mn).
Расстояние редактирования
Levenshtein distance: минимум операций (вставка, удаление, замена) для преобразования строки X в Y. DP: dp[i][j] = min(insert, delete, replace). O(mn). Применение: spell-check, diff, биоинформатика.
LCS в diff/patch
Алгоритм diff (Douglas McIlroy, 1974): находит минимальные изменения между файлами через LCS строк. Применение: git diff, svn, version control, DNA sequence alignment (биоинформатика). Вывод: + добавленные строки, − удалённые. O(mn) память, оптимизации: Hunt-McIlroy O((m+n)·D).
Расстояние редактирования (Levenshtein)
Минимум операций (вставка, удаление, замена) для преобразования строки A в B. DP: d[i][j] = min(d[i−1][j]+1, d[i][j−1]+1, d[i−1][j−1]+cost). Применение: spell check (Did you mean?), поиск похожих последовательностей (DNA), fuzzy matching. Damerau-Levenshtein: +транспозиция.
Восстановление LCS через backtracking
После заполнения DP таблицы: начать с dp[m][n]. Если s1[i-1] == s2[j-1], добавить символ в результат, i--, j--. Иначе: двигаться к max(dp[i-1][j], dp[i][j-1]). Пример: s1 = "ABCDGH", s2 = "AEDFHR" → dp[6][6] = 3, восстановление: "ADH". Сложность: O(m+n) для backtracking. Применение: diff утилита (git diff), сравнение ДНК.
Алгоритм LIS
Longest Increasing Subsequence: наибольшая возрастающая подпоследовательность. O(n²) DP: dp[i] = max(dp[j]+1) для j < i, arr[j] < arr[i]. O(n log n): бинарный поиск + массив tail (наименьшие концы возрастающих последовательностей).

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

❓Часто задаваемые вопросы

LCS — наибольшая общая подпоследовательность — это тема о правилах, механизмах и практиках в своей области. Она помогает понять, как принимаются решения и к каким последствиям они приводят.

🔗Узнать больше

YouTube

Что такое LCS — наибольшая общая подпоследовательность Лекция об lcs — наибольшая общая подпоследовательность LCS — наибольшая общая подпоследовательность: разбор

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

Содержание карты

❓Часто задаваемые вопросы

🔗Узнать больше