3

2 つのシーケンス間の最長の共通部分シーケンスを見つけるために、動的計画法のアプローチを実装しようとしました。私のアルゴリズムは、比較される 2 つの文字列が同じ長さの場合に機能しますが、2 番目の文字列が最初の文字列よりも長い場合、LCSLength()関数は正しい値を返しません。

間違った値を返すテスト ケースを含むコードを次に示します。

#include <iostream>
#include <string>
#include <fstream>

using namespace std;

int LCSLength(string X,string Y);

int main()
{
    string first ("HELLO");
    string second ("HLOCKKE");
    int LCS;

    //ifstream inData;
    //inData.open("test.dat");

    //inData >> first >> second;
    //inData.close();

    LCS = LCSLength(first,second);
    cout << "The LCS is: " << LCS << endl;
    cout << first << endl;
    cout << second << endl;
    return 0;
}

int LCSLength(string X,string Y)
{
    int m = X.size();
    int n = Y.size();
    int C[m][n];
    for(int i=0; i<=m; i++)
    {
        for(int j=0; j<=n; j++)
            C[i][j] = 0;
    }
    for(int i=1; i<=m; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(X[i-1]==Y[j-1])
                C[i][j]=C[i-1][j-1]+1;
            else 
                C[i][j]=max(C[i][j-1],C[i-1][j]);
       }
    }

    return C[m][n];
}

2 つの文字列間の LCS が 3 であるため、これは "The LCS is: 3" を出力するはずですが、私のプログラムはそうではありません。エラーが見つかりません。ご協力ありがとうございました。

4

1 に答える 1

5

いくつかの Google 検索を使用してエラーを修正しました。インデックス作成は私の問題でした。正しいコードは次のとおりです。

#include <iostream>
#include <string>
#include <fstream>


using namespace std;

int LCSLength(string X,string Y);

int main()
{
    string first ("HELLO");
    string second ("HLOCKKE");
    int LCS;

    //ifstream inData;
    //inData.open("test.dat");

    //inData >> first >> second;
    //inData.close();

    LCS = LCSLength(first,second);
    cout << "The LCS is: " << LCS << endl;
    cout << first << endl;
    cout << second << endl;
    return 0;
}

int LCSLength(string X,string Y)
{
    int m = X.size();
    int n = Y.size();
    int L[m+1][n+1];
    for(int i=0; i<=m; i++)
    {
        for(int 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]);
        }
    }
    return L[m][n];
}
于 2012-12-05T10:57:02.760 に答える