Самая длинная общая подпоследовательность: Python, C++ Пример

Что такое самая длинная общая подпоследовательность?

Поиск самой длинной общей подпоследовательности (LCS) означает, что вам будут даны две строки, шаблона или последовательности объектов. Среди этих двух последовательностей или строк вам нужно найти самую длинную подпоследовательность элементов в том же порядке, которые присутствуют в обеих строках или шаблонах.

Пример

Например, предоставлены две строки. Предположим, что:

Узор_1 = «РГБГАРГА»
Шаблон_2 = «БГРАРГ»

• На основе pattern_1 можно создавать последовательности типа «RGB», «RGGA», «RGAR». Для создания последовательности необходимо сохранять относительное положение каждого символа в строке.
• Из pattern_2 можно получить последовательности типа “BGR”, “BRAG”, “RARG”. Последовательности могут быть созданы при условии сохранения относительного положения исходной строки.

Термин относительное положение означает порядок.

Например, последовательность «BRG» является допустимой, поскольку в исходной строке pattern_2 сначала идет «B», затем «R», а затем «G». Однако, если последовательность — «RBRG», она недопустима, поскольку в исходной строке (pattern_2) «B» идет первой.

У нас есть два варианта найти самую длинную общую подпоследовательность из данных двух последовательностей или массивов.

• Наивный метод
• Решение для динамического программирования: самая длинная общая подпоследовательность также известна как LCS.

Наивное решение имеет большую временную сложность и не является оптимальным. Используя метод динамического программирования (ДП), мы преодолеваем проблему сложности.

Наивный метод

Наивный метод — это простой подход к решению проблемы, не зависящий от временной сложности и других факторов оптимизации. В большинстве случаев он состоит из «грубой силы», множества циклов и рекурсивных вызовов. Термин «грубая сила» означает перебор всех возможных вариантов решения данной задачи.

Пример

Из приведенного выше примера шаблона1 и шаблона2 предположим, что шаблон1 имеет длину m, а шаблон2 имеет длину n. Чтобы проверить все возможные случаи, нам нужно оценить каждую возможную подпоследовательность шаблона 1 с помощью шаблона 2.

Вот простая четырехбуквенная строка «ABCD». Например, нам нужно составить последовательность из «ABCD». Мы можем либо взять символ, либо нет. Это значит, что для каждого символа у нас есть два варианта:

• Персонаж будет добавлен в подпоследовательность.
• Символ не будет добавлен в подпоследовательность.

Здесь изображения показывают все последовательности, которые мы можем составить из строки «ABCD».

Последовательность из 1 символа:

Последовательности из 2 символов:

Последовательности из 3 символов:

На приведенной выше диаграмме показано 14 последовательностей. Если мы не возьмем ни одной буквы, то есть пустую строку, то общее количество последовательностей составит 15. Более того, сама строка «ABCD» является последовательностью. Таким образом, общее количество последовательностей равно 16.

Таким образом, из "ABCD" можно сгенерировать 2^4 или 16 подпоследовательностей. Затем получится строка длиной m будет иметь в общей сложности 2^m подпоследовательность.

Для каждой подпоследовательности нам необходимо проверить ее на протяжении всего шаблона2. Это займет время O(n). O(n) означает функцию сложности, которая вычисляет время, необходимое для выполнения.

Таким образом, общая временная сложность становится O(n*2^m). В приведенном выше примере значение m=8, а n=5.

Вот шаги наивного метода:

Шаг 1) Возьмите последовательность из шаблона 1.
Шаг 2) Сопоставьте последовательность из шага 1 с шаблоном 2.
Шаг 3) Если оно совпадает, сохраните подпоследовательность.
Шаг 4) Если в шаблоне pattern1 осталось еще несколько последовательностей, то вернитесь к шагу 1.
Шаг 5) Выведите самую длинную подпоследовательность.

Оптимальная основа

Термин «оптимальная подструктура» означает, что оптимальное решение может быть найдено путем решения подзадач. Например, в приведенном выше примере у нас есть шаблон 1 и шаблон 2.

Шаг 1) Возьмите первые два символа из каждого шаблона.

Шаг 2) Возьмите третий-пятый символы из каждого шаблона.

Шаг 3) Продолжайте аналогично с остальными персонажами.

Рекурсивная структура задачи LCS

Мы находим наименьшую общую кратность (НОК) подстроки (строки, сгенерированной из исходной строки). Затем мы сохраняем запись о длине НОК подстроки.

А вот еще одно интересное свойство: перекрытиеping подзадачиГоворят, что проблема имеет перекрытие.ping подзадачи, если условие задачи можно разбить на небольшие подзадачи и использовать несколько раз в программе.

На диаграмме ниже показано, что рекурсивный алгоритм несколько раз вызывал функцию с одним и тем же параметром.

Например, взгляните на дерево рекурсии. В темном прямоугольнике вы можете заметить перекрытие.ping Подзадачи («РГ», «РА»), («РГ», «Р») и другие упоминаются несколько раз.

Для оптимизации этого процесса мы используем следующий подход: Динамическое программирование (ДП).

Рекурсивный метод нахождения самой длинной общей подпоследовательности

Представленный выше график иллюстрирует рекурсивный метод. Каждая рекурсивная функция имеет базовый случай для прерывания рекурсии или начала возврата из стека.

Для этой реализации мы будем использовать базовый случай. Итак, алгоритм выглядит следующим образом:

• Если все элементы перед последним элементом имеют совпадение, то увеличьте длину на единицу и верните значение.
• Передайте в функцию два шаблона и возьмите максимальное значение из возвращаемого значения.
• Если один шаблон имеет нулевую длину, то у нас нет подпоследовательности для сравнения. В этом случае верните 0. Это базовый случай рекурсии.

Прозвище Code:

def lcs:
    input: pattern_1, pattern_2, len_1, len_2
    if len_1 or len_2 is zero:
        return 0
    if pattern_1[len_1 - 1] equals pattern_2[len_2 - 1]:
        return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1)
    else:
        return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2),
                   lcs(pattern_1, pattern_2, len_1, len_2 - 1))

Реализация в C++

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int lcs(string pattern_1, string pattern_2, int len_1, int len_2) {
  if (len_1 == 0 || len_2 == 0)
    return 0;
  if (pattern_1[len_1 - 1] == pattern_2[len_2 - 1]) {
    return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1);
  } else {
    return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1));
  }
}
int main() {
  string pattern_1, pattern_2;
  pattern_1 = "RGBGARGA";
  pattern_2 = "BGRARG";
  cout<<"Length of LCS is: "<<lcs(pattern_1, pattern_2, pattern_1.size(), pattern_2.size())<<endl;
}

Выход:

Length of LCS is: 5

Реализация в Python

def lcs(pattern_1, pattern_2, len_1, len_2):
    if len_1 == 0 or len_2 == 0:
        return 0
    if pattern_1[len_1 - 1] == pattern_2[len_2 - 1]:
        return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1)
    else:
        return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2),
                   lcs(pattern_1, pattern_2, len_1, len_2 - 1))

pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Length of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

Выход:

Length of LCS is:  5

Метод динамического программирования для поиска самой длинной общей подпоследовательности (LCS)

Динамическое программирование подразумевает оптимизацию обычного рекурсивного метода. Например, если мы посмотрим на граф рекурсивного или наивного подхода, мы увидим несколько идентичных вызовов функций. Метод динамического программирования записывает все вычисления в массив и повторно использует их при необходимости.

Мы будем использовать двумерный массив размером m х n, где m и n — длины шаблонов pattern1 и pattern2. 2D массивмы можем использовать структуры данных List в Python или структуры данных вектора/массива в C++.

Прозвище Code для LCS с использованием DP:

LCS(pattern_1, pattern_2):
    m = length of pattern_1 + 1
    n = length of pattern_2 + 1
    dp[n][m]
    for i in range 0 to n + 1:
        for j in range 0 to m + 1:
            if i or j equals to 0:
                dp[i][j] = 0
            else if pattern_1[i] == pattern_2[j]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

Здесь представлена ​​таблица LCS, используемая в качестве двумерного массива данных для подхода динамического программирования.

Давайте обсудим логику, которую мы здесь использовали. Шаги следующие:

Шаг 1) Если i или j равно нулю, мы берем пустую строку из двух заданных строк и пытаемся найти общие подпоследовательности. Однако, поскольку беремая подстрока пуста, длина подпоследовательности равна 0.

Шаг 2) Если два символа совпадают, мы присвоим значение индексу (i,j), увеличив ранее вычисленную LCS, которая находится в индексе (i-1,j-1) (из предыдущей строки).

Шаг 3) Если совпадений нет, то мы возьмем максимальное значение наименьшего общего кратного (LCS) из двух смежных индексов. Таким образом, нам нужно заполнить все значения в двумерном массиве.

Шаг 4) Наконец, мы вернем значение последней ячейки двумерного массива.

По сути, все значения в двумерном массиве содержат длину общих подпоследовательностей. При этом в последней ячейке указана длина самой длинной общей подпоследовательности.

Реализация в C++

#include<iostream>
using namespace std;
int lcs(string pattern_1, string pattern_2) {
  int m = pattern_1.size();
  int n = pattern_2.size();
  // dp will store solutions as the iteration goes on
  int dp[n + 1][m + 1];
  for (int i = 0; i < n + 1; i++) {
    for (int j = 0; j < m + 1; j++) {
      if (i == 0 || j == 0) {
        dp[i][j] = 0;
      } else if (pattern_2[i - 1] == pattern_1[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[n][m];
}
int main() {
  string pattern_1 = "RGBGARGA";
  string pattern_2 = "BGRARG";
  cout<<"Length of LCS: "<<lcs(pattern_1, pattern_2)<<endl;
}

Выход:

Length of LCS: 5

Реализация в Python

def lcs(pattern_1, pattern_2):
    m = len(pattern_1)
    n = len(pattern_2)
    # dp will store solutions as the iteration goes on
    dp = [[None] * (n + 1) for item in range(m + 1)]
    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif pattern_1[i - 1] == pattern_2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Length of LCS: ", lcs(pattern_1, pattern_2))

Выход:

Length of LCS: 5

Итак, обе строки имеют самую длинную общую подпоследовательность длиной 5.

Вкратце, в методе динамического программирования мы просто выполняем каждую задачу один раз. В рекурсивном методе может возникнуть перекрытие.ping подзадачи.

В этом алгоритме динамического программирования мы используем двумерную матрицу. Будет дано две строки (предположим, что обе имеют длину n). Тогда необходимое пространство в массиве равно nx n. Если строки достаточно велики, нам понадобится версия решения DP, оптимизированная для памяти.

Упрощенная логика, которая была использована в коде:

• Объявите двумерный массив DP[m][n].
• Заполните первую строку и первый столбец массива DP значениями 0.
• Возьмите i и j для итерации.
• Если pattern1[i] равен pattern2[j], то обновите DP[i][j] = DP[i-1][j-1] + 1.
• Если pattern1[i] не равен pattern2[j], то DP[i][j] будет максимальным значением между DP[i-1][j] и DP[i][j-1].
• Продолжайте, пока i и j не достигнут m и n.
• Последний элемент, DP[m-1][n-1], будет содержать длину.

Здесь он обозначается как DP[m-1][n-1], поскольку индекс массива начинается с 0.

Часто задаваемые вопросы (FAQ)