1

与えられた 2 つの文字列で最長共通サブシーケンスの最大長を見つける問題を解決するプログラムに取り組んでいますが、結果の行列に 2 つの文字列の最初の文字が表示されないことがわかりました。

例 - 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");
    }

コードはすべての文字列に対して正しい結果を返していますが、提供された入力文字列名が結果に表示されず、両方の文字列の最初の文字がスキップされます。残念ながら、この動作の理由はわかりません。解決するのを手伝ってくださいこの問題。
ありがとう

4

3 に答える 3

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]));
    }
于 2013-06-01T18:55:22.217 に答える
0

あなたの A[0] = ' ' は、最初の入力文字列の最初の文字を上書きしています。B の場合、最初の印刷ループは i =1 から始まりますが、2 番目の文字列の最初の文字が欠落しています。

于 2013-06-01T18:44:39.170 に答える