c - 我查找 LCS 的代码返回一个空矩阵

Question

我正在编写一个代码来查找两个字符串之间的最长公共子序列，为此目的创建了一个矩阵。这个想法是，对于每个位置 [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;
}

标签： clcs