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

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

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

Пример

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

Давайте предположим, что,

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

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

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

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

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

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

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

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

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

Наивный метод состоит из «грубой силы», множества циклов и в большинстве случаев рекурсивных методов.

Термин «грубая сила» означает перебор всех возможных шаблонов решения данной проблемы.

Пример

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

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

К ним относятся:

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

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

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

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

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

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

Итак, можно создать 2⁴ или 16 подпоследовательностей из «ABCD». Затем строка длиной m придется составить подпоследовательность из 2^m.

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

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

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

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

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

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

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

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

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

Мы находим LCS на подстроке (строке, сгенерированной из исходной строки). Затем ведем учет длины ЛСК подстрок.

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

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

Например, давайте посмотрим на дерево рекурсии.

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

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

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

График, показанный выше, представляет собой рекурсивный метод. У каждой рекурсивной функции есть базовый вариант, позволяющий прервать рекурсию или начать возврат из стека.

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

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

Псевдокод:

def lcs:
    input: pattern_1, pattern_2, len_1, len_2
if len_1 or len_2 is zero:
    then
return 0
if pattern_1[len_1 - 1] equals pattern_2[len_2 - 1]
then
return 1 + lcs(pattern_1, pattern_2,
    len_1 - 1, len_2 - 1)
else
    max of 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

Реализация на питоне

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("Lenght of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

Вывод:

Lenght of LCS is:  5

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

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

Мы будем использовать двумерный массив размером mxn, где m и n — длины шаблона2 и шаблона1.

Что касается 2D массив, мы можем использовать структуры данных List в Python или структуры данных Vector/Array в C++.

Псевдокод для 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 двух соседних индексов. И таким образом нам нужно заполнить все значения в 2D-массиве.

Шаг 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 & lt; n + 1; i++) {
    for (int j = 0; j & lt; 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.

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

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

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

• Объявите двумерный массив DP[m][n].
• Заполните первую строку и первый столбец массива DP значениями 0.
• Возьмите i и j для итерации.
• Если шаблон1[i] равен шаблону2[j], обновите DP[i][j] = DP[i-1][j-1] + 1.
• Если шаблон1[i] не равен шаблону2[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.

Резюме

• Метод ДП имеет меньшую временную сложность; это O(mn), где m и n — длина входной строки или массива.
• DP — более быстрый подход, чем рекурсивный, с временной сложностью О(п*2^m).
• Динамическое программирование (DP) не оптимизировано для памяти. Мы использовали двумерный массив длиной m*n. Итак, пространственная сложность равна (m*n).
• Рекурсивный метод: в худшем случае максимальная занимаемая им память будет равна m+n, то есть, по сути, общая длина введенной строки.
• Сегодняшнему современному компьютеру достаточно для обработки такого объема памяти.