Längste Gemeinsame Teilfolge der Länge-Funktion nicht wieder die richtige Länge?

Habe ich versucht zu implementieren, die dynamische Programmierung Ansatz zur Suche nach der längsten gemeinsamen sub-Sequenz zwischen zwei Sequenzen. Mein Algorithmus funktioniert, wenn die beiden strings, die verglichen werden, sind die gleichen Längen, aber wenn die zweite Zeichenfolge ist länger als die erste, meine LCSLength() Funktion nicht den richtigen Wert zurück.

Hier ist der code mit einem Testfall, die einen falschen Wert zurück.

#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];
}

Diese gedruckt werden sollen "Die LCS ist: 3" da die LCS zwischen meinen beiden strings ist 3, aber mein Programm nicht. Ich kann nicht finden, mein Fehler. Danke für Eure Hilfe.

  • Ich fand einen Fehler gemacht, den zu Bearbeiten. Noch nicht wieder der korrekte Wert.
  • was braucht es dafür? Und warum erwartest du, dass 3? Ich die längste gemeinsame Teil, den ich sehen kann, ist LO die 2
  • Ich erwarte 3 weil der längsten gemeinsamen Teilfolge ist HLO. Für dieses Besondere Beispiel, mein Programm gibt 4.
  • en.wikipedia.org/wiki/Longest_common_subsequence_problem
  • Ich habe versucht, die wiki-Implementierung schon. Nicht für mich arbeiten. Vielleicht meinen die Indizierung ausgeschaltet ist, irgendwo?
  • Ich sehe nicht, wie dein code funktionieren soll in den ersten Platz. Sie gegen Grenzen Ihrer C[m][n] array ist ein nicht definiertes Verhalten
  • Du hast Recht. Ich fand meine restlichen Fehler und posted die richtige Lösung. Danke.

InformationsquelleAutor Zack | 2012-12-05
Schreibe einen Kommentar