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

Dieses Thema im Forum "Programmierung & Entwicklung" wurde erstellt von Gutschy, 9. Februar 2017 .

Schlagworte:
  1. 9. Februar 2017
    Zuletzt von einem Moderator bearbeitet: 13. April 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.

    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
     
  2. 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
     
  3. Video Script

    Videos zum Themenbereich

    * gefundene Videos auf YouTube, anhand der Überschrift.