Good-Suffix Table (Boyer-Moore) von C => C++

[Lemieux]

Hallo!
Ich muss den Boyer-Moore Algorithmus aus dem Wikipedia (http://de.wikipedia.org/wiki/Boyer-Moore-Algorithmus) in C++ implementieren und soll mit strings arbeiten und auf die gotos verzichten.
Habe das mal versucht und leider stimmt bei mir irgendetwas nicht. Meiner Meinung nach müsste der Code funktionieren, habe wohl irgendwo nen Logikfehler eingebaut...

Weiß einer von euch ne Antwort?

C:

next = (int*)malloc((plen+1) * sizeof(int));

for (j = 0; j <= plen; j++) {
   for (i = plen - 1; i >= 1; i--) {
     for (k = 1; k <= j; k++) {
       if (i - k < 0) goto matched;
       if (p[plen - k] != p[i - k]) goto nexttry;
     }
   goto matched;
   nexttry: ;
   }
   matched: next[j] = plen - i;
 }

Werte:

next[0] = 1
next[1] = 4
next[2] = 4
next[3] = 6
next[4] = 6
next[5] = 6
next[6] = 6
next[7] = 6

Meine Lösung:

cout << endl << "GoodRule Table:" << endl;
	next = new int((patternLength + 1) * sizeof(int));

	for (j = 0; j <= patternLength; j++) {
		i = patternLength - 1;
		bool matched = false;

		while (i >= 1 && matched == false) {
			k = 1;
			bool nexttry = false;

			while (k <= j && matched == false && nexttry == false) {
				if (i - k < 0)
					matched = true;

				if (pattern[patternLength - k] != pattern[i - k])
					nexttry = true;

				k++;
			}

			if (nexttry == false)
				matched = true;

			i--;
		}
		next[j] = patternLength - i + 1;
		cout << "next[" << j << "] = " << next[j] << endl;
	}

Werte:

next[0] = 3
next[1] = 6
next[2] = 6
next[3] = 8
next[4] = 8
next[5] = 8
next[6] = 8
next[7] = 8

Wie ihr seht, ist meine Lösung alles andere als elegant, was könnt ich verbessern?

Wäre sehr dankbar!

lg,
Lemieux

[Gast]

Hi Lemieux,

mir sind so ein paar Sachen an deinem Code aufgefallen:

cout << endl << "GoodRule Table:" << endl;
    next = new int((patternLength + 1) /* * sizeof(int)*/); // mehr Speicher als nötig

    for (j = 0; j <= patternLength; j++) {
        i = patternLength - 1;
        bool matched = false;

        while (i >= 1 && matched == false) {
            k = 1;
            bool nexttry = false;

            while (k <= j && matched == false && nexttry == false) {
                if (i - k < 0)
                    matched = true;

                /*else*/ if (pattern[patternLength - k] != pattern[i - k])
                    nexttry = true;

                /* else */k++; // Diese Zeile wird auch ausgeführt, wenn matched oder nexttry gesetzt werden (im Gegensatz zu Original)
            }

            if (nexttry == false)
                matched = true;
            /* if(!matched)*/
                i--; // analog zu oben
        }
        next[j] = patternLength - i + 1;
        cout << "next[" << j << "] = " << next[j] << endl;
    }

Ich bin mir nicht sicher, ob das Ergebnis jetzt richtig ist, aber es sollte sich
(mindestens) um eins nach unten verschieben.

Gruß,
CSpille

[DrakoXP]

next = new int((patternLength + 1); // -> * sizeof(int)) musst du hier weglassen!
for (j = 0; j < patternLength; j++) {
    bool matched = false;
    for (i = patternLength - 1; i > 1 && matched == false; i--) {
        bool nexttry = false;
        for (k = 1; k <= j && matched == false && nexttry == false; k++) {
            if (i - k < 0) matched = true;
            else if (pattern[patternLength - k] != pattern[i - k]) nexttry = true;
        }
    }
    next[j] = patternLength - i + 1;
    cout << "next[" << j << "] = " << next[j] << endl;
}

der code ist ungetestet und hat keinen Stil, trotzdem denke ich, dass es jetzt funktioniert...

MfG DrakoXP

[Lemieux]

CSpille schrieb:

Hi Lemieux,

mir sind so ein paar Sachen an deinem Code aufgefallen:

cout << endl << "GoodRule Table:" << endl;
    next = new int((patternLength + 1) /* * sizeof(int)*/); // mehr Speicher als nötig
    
    for (j = 0; j <= patternLength; j++) {
        i = patternLength - 1;
        bool matched = false;
        
        while (i >= 1 && matched == false) {
            k = 1;
            bool nexttry = false;
            
            while (k <= j && matched == false && nexttry == false) {
                if (i - k < 0)
                    matched = true;
                
                /*else*/ if (pattern[patternLength - k] != pattern[i - k])
                    nexttry = true;
                
                /* else */k++; // Diese Zeile wird auch ausgeführt, wenn matched oder nexttry gesetzt werden (im Gegensatz zu Original)
            }
            
            if (nexttry == false)
                matched = true;
            /* if(!matched)*/
                i--; // analog zu oben
        }
        next[j] = patternLength - i + 1;
        cout << "next[" << j << "] = " << next[j] << endl;
    }

Ich bin mir nicht sicher, ob das Ergebnis jetzt richtig ist, aber es sollte sich
(mindestens) um eins nach unten verschieben.

Gruß,
CSpille

Funktioniert! Danke!

Danke auch an DrakoXP, hat aber nicht funktioniert