Мой код для поиска LCS возвращает нулевую матрицу - PullRequest
Новая
       5

Мой код для поиска LCS возвращает нулевую матрицу

0 голосов
/ 29 октября 2019

Я делаю код, чтобы найти самую длинную общую подпоследовательность между двумя строками, которая создает матрицу для этой цели. Идея состоит в том, что для каждой позиции [i] [j] вы определяете значение этой позиции как наибольшую сумму (или путь) до этого пути и добавляете 1, если элементы в матрицах совпадают. Однако, когда я запускаю этот код, он возвращает матрицу с "NULL" в каждой позиции. Может ли кто-нибудь разъяснить мне это? Заранее спасибо! 

//Part 1
//Implements the LCS (Longest common subsequence) algorithm
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main()
{
    //Initializes two DNA strings to use for trial
    char string_1[]="ATTCTTTAGCAGGCAGGCAGGTGGCAGGTGACGATGGGGATGGAAAAG";
    char string_2[]="ATACTTTAGCATGCGGGCAGGAGGCGAGACGATGTCGGTATGAATG";

    //We want a matrix [m+1][n+1], where string_1[m] and string_2[n]
    //because m = strlen(string_1) + 1 and n = strlen(string_2) +1
    //We create a matrix [strlen(string_1) +2][strlen(string_2)+2]
    int m = strlen(string_1)+2;
    int n = strlen(string_2)+2;
    char lcs_matrix[m][n];

    //We initialize the lcs_matrix
    for (int i=0; i<m; i++)
    {
        for (int j=0; j<n; j++)
        {
            //For all the elements in the first column and line we set the value equal to zero
            if ((i==0)||(j==0))
            {
                lcs_matrix[i][j] = 0;
            }
            //If the elements of the strings match (are equal), we define the value of the 
            //[i][j] position as the previous [i-1][j-1] position + 1
            else if (string_1[i-1] == string_2[j-1])
            {
                lcs_matrix[i][j] = lcs_matrix[i-1][j-1] + 1;
            }
            //If the elements don't match, we define the value of the position 
            //[i][j] to be the value of the greatest of the previous values horizontally or vertically
            else
            {
                if (lcs_matrix[i-1][j] >= lcs_matrix[i][j-1])
                {
                    lcs_matrix[i][j] = lcs_matrix[i-1][j];
                }
                else
                {
                    lcs_matrix[i][j] = lcs_matrix[i][j-1];
                }
            }


        }

    }
    //I print the final matrix
    for (int i=0; i<m; i++)
    {
        for (int j=0; j<n; j++)
        {
            printf("%s ", lcs_matrix[i][j]);
        }
        printf("\n");
    }
    system("pause");
    return 0;
}
...