Рубрики

Печать самой длинной общей подпоследовательности

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

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

Мы обсуждали проблему Longest Common Subsequence (LCS) в предыдущем посте . Обсуждаемая функция была в основном для определения длины LCS. Чтобы найти длину LCS, была построена двухмерная таблица L [] []. В этом посте обсуждается функция построения и печати LCS.

Ниже приведен подробный алгоритм печати LCS. Он использует ту же 2D таблицу L [] [].

1) Постройте L [m + 1] [n + 1], используя шаги, описанные в предыдущем посте .

2) Значение L [m] [n] содержит длину LCS. Создайте массив символов lcs [] длиной, равной длине lcs плюс 1 (один дополнительный для сохранения / 0).

2) Перейдите 2D массив, начиная с L [m] [n]. Делайте следующее для каждой ячейки L [i] [j]
… .. a) Если символы (в X и Y), соответствующие L [i] [j], одинаковы (или X [i-1] == Y [j-1]), то включите этот символ как часть LCS ,
… .. b) В противном случае сравните значения L [i-1] [j] и L [i] [j-1] и перейдите в направлении большего значения.

В следующей таблице (взято из Wiki ) показаны шаги (выделены), за которыми следует приведенный выше алгоритм.

01234567
ØMZJAWXU
0Ø00000000
1X00000011
2M01111111
3J01122222
4Y01122222
5A01123333
6U01123334
7Z01223334

Ниже приводится реализация вышеуказанного подхода.

C / C ++

/ * Динамическое программирование реализации задачи LCS * /
#include<iostream>
#include<cstring>
#include<cstdlib>

using namespace std;

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

void lcs( char *X, char *Y, int m, int n )

{

   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]);

     }

   }

  

   // Следующий код используется для печати LCS

   int index = L[m][n];

  

   // Создаем массив символов для хранения строки lcs

   char lcs[index+1];

   lcs[index] = '\0'; // Устанавливаем завершающий символ

  

   // Начинаем с самого правого-самого нижнего угла и

   // один за другим сохраняем символы в lcs []

   int i = m, j = n;

   while (i > 0 && j > 0)

   {

      // Если текущий символ в X [] и Y совпадает, то

      // текущий символ является частью LCS

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

      {

          lcs[index-1] = X[i-1]; // Поместить текущий символ в результат

          i--; j--; index--;     // уменьшаем значения i, j и index

      }

  

      // Если не одно и то же, то найти большее из двух и

      // идти в направлении большего значения

      else if (L[i-1][j] > L[i][j-1])

         i--;

      else

         j--;

   }

  

   // Распечатать lcs

   cout << "LCS of " << X << " and " << Y << " is " << lcs;

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

  char X[] = "AGGTAB";

  char Y[] = "GXTXAYB";

  int m = strlen(X);

  int n = strlen(Y);

  lcs(X, Y, m, n);

  return 0;

}

Джава

// Динамическое программирование реализации задачи LCS в Java

import java.io.*;

  

class  LongestCommonSubsequence

{

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

    static void lcs(String X, String Y, int m, int n)

    {

        int[][] L = new int[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.charAt(i-1) == Y.charAt(j-1))

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

                else

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

            }

        }

   

        // Следующий код используется для печати LCS

        int index = L[m][n];

        int temp = index;

   

        // Создаем массив символов для хранения строки lcs

        char[] lcs = new char[index+1];

        lcs[index] = ''; // Устанавливаем завершающий символ

   

        // Начинаем с самого правого-самого нижнего угла и

        // один за другим сохраняем символы в lcs []

        int i = m, j = n;

        while (i > 0 && j > 0)

        {

            // Если текущий символ в X [] и Y совпадает, то

            // текущий символ является частью LCS

            if (X.charAt(i-1) == Y.charAt(j-1))

            {

                // Поместить текущий символ в результат

                lcs[index-1] = X.charAt(i-1); 

                  

                // уменьшаем значения i, j и index

                i--; 

                j--; 

                index--;     

            }

   

            // Если не одно и то же, то найти большее из двух и

            // идти в направлении большего значения

            else if (L[i-1][j] > L[i][j-1])

                i--;

            else

                j--;

        }

   

        // Распечатать lcs

        System.out.print("LCS of "+X+" and "+Y+" is ");

        for(int k=0;k<=temp;k++)

            System.out.print(lcs[k]);

    }

      

    // драйверная программа

    public static void main (String[] args) 

    {

        String X = "AGGTAB";

        String Y = "GXTXAYB";

        int m = X.length();

        int n = Y.length();

        lcs(X, Y, m, n);

    }

}

  
// Предоставлено Прамод Кумар

питон

# Динамическое программирование реализации задачи LCS

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

def lcs(X, Y, m, n):

    L = [[0 for x in xrange(n+1)] for x in xrange(m+1)]

  

    # Следуя шагам, постройте L [m + 1] [n + 1] снизу вверх. Заметка

    # что L [i] [j] содержит длину LCS из X [0..i-1] и Y [0..j-1]

    for i in xrange(m+1):

        for j in xrange(n+1):

            if i == 0 or j == 0:

                L[i][j] = 0

            elif 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])

  

    # Следующий код используется для печати LCS

    index = L[m][n]

  

    # Создать массив символов для хранения строки lcs

    lcs = [""] * (index+1)

    lcs[index] = ""

  

    # Начните с самого правого-самого нижнего угла и

    # один за другим сохраняем символы в lcs []

    i = m

    j = n

    while i > 0 and j > 0:

  

        # Если текущий символ в X [] и Y совпадает, то

        # текущий символ является частью LCS

        if X[i-1] == Y[j-1]:

            lcs[index-1] = X[i-1]

            i-=1

            j-=1

            index-=1

  

        # Если не то же самое, то найдите большее из двух и

        # идти в направлении большего значения

        elif L[i-1][j] > L[i][j-1]:

            i-=1

        else:

            j-=1

  

    print "LCS of " + X + " and " + Y + " is " + "".join(lcs) 

  
# Драйверная программа

X = "AGGTAB"

Y = "GXTXAYB"

m = len(X)

n = len(Y)

lcs(X, Y, m, n)

  
# Этот код предоставлен BHAVYA JAIN

C #

// Динамическое программирование реализации
// проблемы LCS в C #

using System;

  

class GFG

{

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

    static void lcs(String X, String Y, int m, int n)

    {

        int[,] L = new int[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] = Math.Max(L[i-1, j], L[i, j-1]);

            }

        }

  

        // Следующий код используется для печати LCS

        int index = L[m, n];

        int temp = index;

  

        // Создать массив символов

        // для сохранения строки lcs

        char[] lcs = new char[index+1];

          

        // Устанавливаем завершающий символ

        lcs[index] = '\0'

  

        // Начинаем с самого правого-самого нижнего угла

        // и один за другим сохраняем символы в lcs []

        int k = m, l = n;

        while (k > 0 && l > 0)

        {

            // Если текущий символ в X [] и Y

            // одинаковы, то текущий символ

            // является частью LCS

            if (X[k-1] == Y[l-1])

            {

                // Поместить текущий символ в результат

                lcs[index-1] = X[k-1]; 

                  

                // уменьшаем значения i, j и index

                k--; 

                l--; 

                index--;     

            }

  

            // Если не одно и то же, то найти большее из двух и

            // идти в направлении большего значения

            else if (L[k-1, l] > L[k, l-1])

                k--;

            else

                l--;

        }

  

        // Распечатать lcs

        Console.Write("LCS of " + X + " and " + Y + " is ");

        for(int q = 0; q <= temp; q++)

            Console.Write(lcs[q]);

    }

      

    // Драйвер программы

    public static void Main () 

    {

        String X = "AGGTAB";

        String Y = "GXTXAYB";

        int m = X.Length;

        int n = Y.Length;

        lcs(X, Y, m, n);

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php 
// Динамическое программирование реализации задачи LCS

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

function lcs( $X, $Y, $m, $n )

{

    $L = array_fill(0, $m + 1, 

         array_fill(0, $n + 1, NULL));

      

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

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

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

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

    {

        for ($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]);

        }

    }

      

    // Следующий код используется для печати LCS

    $index = $L[$m][$n];

    $temp = $index;

      

    // Создаем массив символов для хранения строки lcs

    $lcs = array_fill(0, $index + 1, NULL);

    $lcs[$index] = ''; // Устанавливаем завершающий символ

      

    // Начинаем с самого правого-самого нижнего угла

    // и один за другим сохраняем символы в lcs []

    $i = $m;

    $j = $n;

    while ($i > 0 && $j > 0)

    {

        // Если текущий символ в X [] и Y совпадает,

        // тогда текущий символ является частью LCS

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

        {

            // Поместить текущий символ в результат

            $lcs[$index - 1] = $X[$i - 1];

            $i--;

            $j--; 

            $index--;    // уменьшаем значения i, j и index

        }

      

        // Если не одно и то же, то найти большее из двух

        // и идти в направлении большего значения

        else if ($L[$i - 1][$j] > $L[$i][$j - 1])

            $i--;

        else

            $j--;

    }

      

    // Распечатать lcs

    echo "LCS of " . $X . " and " . $Y . " is ";

    for($k = 0; $k < $temp; $k++)

        echo $lcs[$k];

}

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

$X = "AGGTAB";

$Y = "GXTXAYB";

$m = strlen($X);

$n = strlen($Y);

lcs($X, $Y, $m, $n);

  
// Этот код поддерживается ita_c
?>


Выход:

LCS of AGGTAB and GXTXAYB is GTAB

Ссылки:
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

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

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

Печать самой длинной общей подпоследовательности

0.00 (0%) 0 votes