Рубрики

Оптимизированное для космоса решение LCS

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

Примеры:
LCS для входных последовательностей « ABCDGH » и « AEDFHR » — это « ADH » длины 3 .
LCS для входных последовательностей « AGGTAB » и « GXTXAYB » — это « GTAB » длины 4 .

Мы обсудили типичное решение для LCS на основе динамического программирования . Мы можем оптимизировать пространство, используемое проблемой lcs. Мы знаем, что рекуррентное отношение LCS проблема

/ * Возвращает длину LCS для X [0..m-1], Y [0..n-1] * /

int lcs(string &X, string &Y)

{

    int m = X.length(), n = Y.length();

    int L[m+1][n+1];

  

    / * Следуя шагам, строим L [m + 1] [n + 1] снизу вверх

       мода. Обратите внимание, что L [i] [j] содержит длину

       LCS из X [0..i-1] и Y [0..j-1] * /

    for (int i=0; i<=m; i++)

    {

        for (int j=0; j<=n; j++)

        {

            if (i == 0 || j == 0)

                L[i][j] = 0;

  

            else if (X[i-1] == Y[j-1])

                L[i][j] = L[i-1][j-1] + 1;

  

            else

                L[i][j] = max(L[i-1][j], L[i][j-1]);

        }

    }

  

    / * L [m] [n] содержит длину LCS для X [0..n-1] и

       Y [0..m-1] * /

    return L[m][n];

}

Как найти длину LCS в O (n) вспомогательном пространстве?


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

Одно важное наблюдение в реализации выше простой есть, в каждой итерации внешнего цикла мы только значения нужно от всех столбцов предыдущей строки. Таким образом, нет необходимости хранить все строки в нашей матрице DP, мы можем просто хранить две строки за раз и использовать их, таким образом, используемое пространство уменьшится с L [m + 1] [n + 1] до L [2 ] [п + 1]. Ниже приведена реализация вышеуказанной идеи.

C ++

// Пространственно оптимизированная реализация C ++
// проблемы LCS
#include<bits/stdc++.h>

using namespace std;

  
// Возвращает длину LCS
// для X [0..m-1], Y [0..n-1]

int lcs(string &X, string &Y)

{

      

    // Находим длины двух строк

    int m = X.length(), n = Y.length();

  

    int L[2][n + 1];

  

    // Двоичный индекс, используемый для

    // индексировать текущую строку и

    // предыдущая строка

    bool bi;

  

    for (int i = 0; i <= m; i++)

    {

          

        // Вычисляем ток

        // двоичный индекс

        bi = i & 1;

  

        for (int j = 0; j <= n; j++)

        {

            if (i == 0 || j == 0)

                L[bi][j] = 0;

  

            else if (X[i-1] == Y[j-1])

                 L[bi][j] = L[1 - bi][j - 1] + 1;

  

            else

                L[bi][j] = max(L[1 - bi][j], 

                               L[bi][j - 1]);

        }

    }

  

    // Последняя заполненная запись содержит

    // длина LCS

    // для X [0..n-1] и Y [0..m-1]

    return L[bi][n];

}

  
// Код драйвера

int main()

{

    string X = "AGGTAB";

    string Y = "GXTXAYB";

  

    printf("Length of LCS is %d\n", lcs(X, Y));

  

    return 0;

}

Джава

// Java-код для оптимизированного пространства
// Решение LCS

  

class GFG {

      

    // Возвращает длину LCS

    // для X [0..m - 1],

    // Y [0..n - 1]

    public static int lcs(String X, 

                          String Y)

    {

          

        // Находим длины двух строк

        int m = X.length(), n = Y.length();

      

        int L[][] = new int[2][n+1];

      

        // Двоичный индекс, используемый для индексации

        // текущая строка и предыдущая строка.

        int bi=0;

      

        for (int i = 0; i <= m; i++)

        {

              

            // Вычисляем текущий двоичный индекс

            bi = i & 1;

      

            for (int j = 0; j <= n; j++)

            {

                if (i == 0 || j == 0)

                    L[bi][j] = 0;

      

                else if (X.charAt(i - 1) == 

                         Y.charAt(j - 1))

                    L[bi][j] = L[1 - bi][j - 1] + 1;

      

                else

                    L[bi][j] = Math.max(L[1 - bi][j], 

                                        L[bi][j - 1]);

            }

        }

      

        // Последняя заполненная запись содержит длину

        // LCS для X [0..n-1] и Y [0..m-1]

        return L[bi][n];

    }

      

      

    // Код драйвера

    public static void main(String[] args) 

    {

        String X = "AGGTAB";

        String Y = "GXTXAYB";

      

        System.out.println("Length of LCS is " +

                                    lcs(X, Y));

    }

}

  
// Этот код предоставлен Арнавом Кр. Мандал.

python3

# Космический оптимизированный Python
# реализация проблемы LCS

  
# Возвращает длину LCS для
# X [0..m-1], Y [0..n-1]

def lcs(X, Y):

      

    # Найти длину двух строк

    m = len(X)

    n = len(Y)

  

    L = [[0 for i in range(n+1)] for j in range(2)]

  

    # Двоичный индекс, используемый для индексации текущей строки и

    # предыдущая строка

    bi = bool

      

    for i in range(m):

        # Вычислить текущий двоичный индекс

        bi = i&1

  

        for j in range(n+1):

            if (i == 0 or j == 0):

                L[bi][j] = 0

  

            elif (X[i] == Y[j - 1]):

                L[bi][j] = L[1 - bi][j - 1] + 1

  

            else:

                L[bi][j] = max(L[1 - bi][j], 

                               L[bi][j - 1])

  

    # Последняя заполненная запись содержит длину LCS

    # для X [0..n-1] и Y [0..m-1]

    return L[bi][n]

  
Код водителя

X = "AGGTAB"

Y = "GXTXAYB"

  

print("Length of LCS is", lcs(X, Y))

  
# Этот код предоставлен Soumen Ghosh.

C #

// C # код для пробела
// Оптимизированное решение LCS

using System;

  

class GFG

{

      

    // Возвращает длину LCS

    // для X [0..m - 1],

    // Y [0..n - 1]

    public static int lcs(string X,

                          string Y)

    {

          

        // Находим длины

        // две строки

        int m = X.Length, n = Y.Length;

      

        int [,]L = new int[2, n + 1];

      

        // Двоичный индекс, используемый для

        // индексировать текущую строку и

        // предыдущая строка

        int bi = 0;

      

        for (int i = 0; i <= m; i++)

        {

              

            // Вычисляем ток

            // двоичный индекс

            bi = i & 1;

      

            for (int j = 0; j <= n; j++)

            {

                if (i == 0 || j == 0)

                    L[bi, j] = 0;

       

                else if (X[i - 1] == Y[j - 1])

                    L[bi, j] = L[1 - bi, 

                                 j - 1] + 1;

      

                else

                    L[bi, j] = Math.Max(L[1 - bi, j], 

                                        L[bi, j - 1]);

            }

        }

      

        // Последняя заполненная запись содержит

        // длина LCS для X [0..n-1]

        // и Y [0..m-1]

        return L[bi, n];

    }

      

    // Код драйвера

    public static void Main() 

    {

        string X = "AGGTAB";

        string Y = "GXTXAYB";

      

        Console.Write("Length of LCS is " +

                                lcs(X, Y));

    }

}

  
// Этот код добавлен
// от shiv_bhakt.

PHP

<?php
// Пространственно оптимизированная реализация PHP
// проблемы LCS

  
// Возвращает длину LCS
// для X [0..m-1], Y [0..n-1]

function lcs($X, $Y

      

    // Находим длины двух строк

    $m = strlen($X);

    $n = strlen($Y);

  

    $L = array(array());

  

    // Двоичный индекс, используемый для индексации

    // текущая строка и предыдущая строка.

    for ($i = 0; $i <= $m; $i++) 

    

          

        // Вычисляем текущий двоичный индекс

        $bi = $i & 1; 

  

        for ($j = 0; $j <= $n; $j++) 

        

            if ($i == 0 || $j == 0) 

                $L[$bi][$j] = 0; 

  

            else if ($X[$i - 1] == $Y[$j - 1]) 

                $L[$bi][$j] = $L[1 - $bi][$j - 1] + 1; 

  

            else

                $L[$bi][$j] = max($L[1 - $bi][$j], 

                                  $L[$bi][$j - 1]); 

        

    

  

    // Последняя заполненная запись содержит

    // длина LCS

    // для X [0..n-1] и Y [0..m-1]

    return $L[$bi][$n]; 

  
// Код драйвера

$X = "AGGTAB"

$Y = "GXTXAYB"

  

echo "Length of LCS is : ",

               lcs($X, $Y);

  
// Этот код предоставлен Ryuga
?>


Выход:

Length of LCS is 4

Сложность времени: O (m * n)
Вспомогательное пространство: O (n)

Эта статья предоставлена Шивам Миттал . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Оптимизированное для космоса решение LCS

0.00 (0%) 0 votes