Vollständige Version anzeigen : C: KMP-Algorithmus in C abbilden, geht nur um das Präfix.


Gutschy
09.02.2017, 19:09

Hallo Leute,

stehe mal wieder sehr auf dem Schlauch, habe jetzt gelernt (leider schon vor so einigen Wochen..;) wie der KMP Suchalgorithmus funktioniert. Ist ja auch nicht so schwer. Natürlich auch wie die Präfix Bildung von statten geht. Allerdings kann ich die Beispiele aus diversen Lernvideos irgendwie nicht mit dem C-Code denn ich für die Prefix Bildung kenne unter einen Hut bringen. Also dachte ich mir, könnte ja den Code (ist Pseudo-Code glaube ich..;) aus einem Lernvideo in C umschreiben.;( Na ja, ging halt bis jetzt nicht so gut. Vielleicht hat ja jemand Lust es mir richtig zu erklären? Der Beispiel Code aus dem Video ist hier zu finden und zwar ab Minute 1:22.
;;;youtube~com/watch?v=2ogqPWJSftE
Und hier mal meine Interpretation.
/* id_kmp;c */
#include <stdio;h>
#include <stdlib;h>
#include <string;h>
#define MAX 4096

int kmp_prefix(char *, int);
void kmpSearch(char *);
int sinn[MAX];

/* i = Position im Text */
/* j = Position im Muster */
void kmpSearch(char *wort) {
int i, laenge;
laenge = strlen(wort);
kmp_prefix(wort, laenge);
for(i = 0;i <= laenge; i++) {
printf("sinn[%d] = %d\n", i, sinn[i]);

}
}

int kmp_prefix(char *P, int L) {
int b, a;
sinn[1] = 0;
a = 0;
/*printf("Wort: %s\nLaenge: %d\n", P, L);*/
for(b = 2; b < L; b++) {
while(a > 0 && P[a+1] != P[b]){
a = sinn[a];
}
if (P[a+1] == P[b]){
a = a++;
}
else {
sinn[b] = a;
}
}
}

int main(void) {
kmpSearch("cococolalala");
return EXIT_SUCCESS;
}

Momentan wird nur ein leeres Array ausgegeben.

Grüsse,

gutschy

Hardware Preisvergleich | Amazon Blitzangebote!

Videos zum Thema
Video Loading...
ChillingStream
21.02.2017, 17:56

Wieso benutzt du nicht den code von Wikipedia?

int kmp_search(char text[], char word[]);
void kmp_table(char text[], int table[]);


meine funktionen sehen schon ganz anders aus als deine. Da wird wohl mehr nicht stimmen


Ähnliche Themen zu C: KMP-Algorithmus in C abbilden, geht nur um das Präfix.
  • [C/C++] Präfix/Postfix C
    int main() ausgabe= i=0 j=2 k=1 kann mir einer erklären warum zum teufel i=0 wird? meiner meinung nach muss i=-1 sein. [...]

  • Präfix-Filter
    gleich vorne weg: Deine Suchanfrage erzielte keine Treffer. Bitte versuche es mit anderen Suchbegriffen. Ist es realisierbar eine Art Filter in den UG Bereichen einzubauen, sozusagen auf Höhe der 'Themen-Optionen' und 'Thema durchsuchen'. Also das man im Movie Bereich auf [HD] klickt in der [...]

  • Fun Bereich - Präfix
    Guten Morgen RR, Ich würde es sinnvoll finden, wenn man im Fun Berreich den Präfix "Video" oder etwas in der Art einführen würde, damit man auf den ersten Blick sieht, dass der User ein Video reingestellt hat oder nicht. Überall gibts Präfixe und nur im Fun Bereich nicht. Der Fun B [...]

  • Linux & Mac Präfix
    Hallo RR Team Ich wollte einfach mal vorschlagen das Ihr wenn es machbar ist. Präfixe in dem Linux & MAC Forum einbringt. Es wäre einfacher diese zu unterscheiden, wenn z;b. man beim erstellen als Präfix Linux oder Mac aussuchen könnte. Es ist bei manchen Themen halt schwer zu unterscheiden, [...]



raid-rush.ws | Imprint & Contact pr