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

Gutschy · 9. Februar 2017

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-Video
Und hier mal meine Interpretation.

Code:

/* 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

Anzeige

ChillingStream · 21. Februar 2017

AW: C: KMP-Algorithmus in C abbilden, geht nur um das Präfix.

Wieso benutzt du nicht den code von Wikipedia?

Code:

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

Nützliche Suchen

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

Videos zum Themenbereich