Рубрики

Программа на C ++ для самой длинной общей подпоследовательности

Постановка задачи LCS: Учитывая две последовательности, найдите длину самой длинной подпоследовательности, присутствующей в обеих из них. Подпоследовательность — это последовательность, которая появляется в том же относительном порядке, но не обязательно является смежной. Например, «abc», «abg», «bdf», «aeg», «acefg» и т. Д. Являются подпоследовательностями «abcdefg». Таким образом, строка длиной n имеет 2 ^ n различных возможных подпоследовательностей.

Это классическая проблема информатики, основа diff (программа сравнения файлов, которая выводит различия между двумя файлами) и имеет приложения в биоинформатике.

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

Пусть входными последовательностями являются X [0..m-1] и Y [0..n-1] длин m и n соответственно. И пусть L (X [0..m-1], Y [0..n-1]) будет длиной LCS двух последовательностей X и Y. Ниже приводится рекурсивное определение L (X [0 .. m-1], Y [0..n-1]).

Если последние символы обеих последовательностей совпадают (или X [m-1] == Y [n-1]), то
L (X [0..m-1], Y [0..n-1]) = 1 + L (X [0..m-2], Y [0..n-2])

Если последние символы обеих последовательностей не совпадают (или X [m-1]! = Y [n-1]), то
L (X [0..m-1], Y [0..n-1]) = MAX (L (X [0..m-2], Y [0..n-1]), L ( X [0..m-1], Y [0..n-2])

/ * Наивная рекурсивная реализация задачи LCS * /
#include <bits/stdc++.h>

  

int max(int a, int b);

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

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

{

    if (m == 0 || n == 0)

        return 0;

    if (X[m - 1] == Y[n - 1])

        return 1 + lcs(X, Y, m - 1, n - 1);

    else

        return max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n));

}

  
/ * Функция полезности для получения максимум 2 целых чисел * /

int max(int a, int b)

{

    return (a > b) ? a : b;

}

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

int main()

{

    char X[] = "AGGTAB";

    char Y[] = "GXTXAYB";

  

    int m = strlen(X);

    int n = strlen(Y);

  

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

  

    return 0;

}

Выход:

Length of LCS is 4

Ниже приведена табличная реализация проблемы LCS.

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

  

int max(int a, int b);

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

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

{

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

    int i, j;

  

    / * Следуя шагам, соберите 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]);

        }

    }

  

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

    return L[m][n];

}

  
/ * Функция полезности для получения максимум 2 целых чисел * /

int max(int a, int b)

{

    return (a > b) ? a : b;

}

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

int main()

{

    char X[] = "AGGTAB";

    char Y[] = "GXTXAYB";

  

    int m = strlen(X);

    int n = strlen(Y);

  

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

  

    return 0;

}

Выход:

Length of LCS is 4

Пожалуйста, обратитесь к полной статье о динамическом программировании | Установите 4 (Longest Common Subsequence) для более подробной информации!

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

Программа на C ++ для самой длинной общей подпоследовательности

0.00 (0%) 0 votes