c - 最长公共子序列的代码未正确显示结果

Question

我正在为一个程序工作，该程序解决了在给定的两个字符串中找到最长公共子序列的最大长度的问题，我观察到它没有显示结果矩阵中我的 2 个字符串的第一个字符。

示例 - 两个字符串是

• BDCABA
  
• ABCBDAB
  

结果 -

---

算法没有错误，但我的 C 代码中可能存在一些故障。

代码 -

 #include<stdio.h> 
    #include<string.h> 
    #define size 20 
    char A[size],B[size]; 
    int i,j,A_len,B_len;
    int score[size][size];
    void main() 
    { 
        printf("\tEnter first string\n\t");
        scanf("%s",A);
        printf("\tEnter second string\n\t");
        scanf("%s",B);
        printf("\n");
        A_len = strlen(A); 
        B_len = strlen(B); 
        A[0] = ' ';
        printf("\t      ");
        for(i=1;i<=B_len;i++) 
            printf("%5c",toupper(B[i]));
        printf("\n\n");
        for(i=0;i<=A_len;i++) 
        { 
            for(j=0;j<=B_len;j++) 
            { 
                if(i==0 || j==0) 
                    score[i][j]=0; 
                else if(A[i] == B[j] ) 
                    score[i][j] = score[i-1][j-1] + 1; 
                else 
                {
                    if(score[i][j-1]>score[i-1][j])
                        score[i][j] = score[i][j-1];
                    else
                        score[i][j] = score[i-1][j];
                }
            } 
        }
        for(i=0;i<=A_len;i++)
        {
            printf("\t%c",toupper(A[i]));
            for(j=0;j<=B_len;j++)
                printf("%5d",score[i][j]);
            printf("\n\n"); 
        }
        if(score[A_len][B_len] != 0)
        {
            printf("Longest common subsequence is of %d length :\t",score[A_len][B_len]);
        }
        else
            printf("longest common subsequence not found");
    }

代码为所有字符串返回正确的结果，但它没有在结果中显示输入字符串名称，因为它们提供了，它跳过了两个字符串的第一个字符，不幸的是我没有得到这种行为的理由，请帮我解决这个问题。
谢谢

Answer 1

将此代码附加到代码的第 15 行之后，并删除之前的第 16、17、18 和第 19 行。这是工作。

我想，您面临的问题是因为您正在使用 %s 读取字符串，并且您想在第一个字母之后比较您的字符串，以便您可以在那里放置一个 0，对吗？

---

    for(i=0;i<A_len;i++) 
        temp[i+1] = A[i]; 
    for(i=1;i<=A_len;i++) 
        A[i] = temp[i];
    A[0] = ' ';
    for(i=0;i<B_len;i++) 
        temp[i+1] = B[i]; 
    printf("\t      ");
    for(i=1;i<=B_len;i++) 
    {   
        B[i] = temp[i];
        printf("%5c",toupper(B[i]));
    }

Answer 2

您的 A[0] = ' ' 正在覆盖第一个输入字符串中的第一个字符。对于 B，您的第一个打印循环从 i =1 开始，它再次错过了第二个字符串的第一个字符。

Answer 3

请注意，在 C 中，数组的最低索引始终为 0。因此，您不能设置A[0]=' '，应该以 0 开始循环，并以i<length_X(not <=) 结束循环。

但是，您还应该采用算法逻辑（A[0]==B[0] 不是错过，因此i==0|j==0没有理由设置score为 0。