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. Diese Seite verwendet Cookies. Wenn du dich weiterhin auf dieser Seite aufhältst, akzeptierst du unseren Einsatz von Cookies. Weitere Informationen
  1. Gutschy
    Gutschy Neu
    Stammnutzer
    #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. Anzeige
  3. ChillingStream
    ChillingStream Neu
    Stammnutzer
    #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
     

  4. Videos zum Thema
Die Seite wird geladen...
Similar Threads - Algorithmus abbilden geht
  1. Antworten:
    2
    Aufrufe:
    1.153
  2. Antworten:
    3
    Aufrufe:
    1.506
  3. Antworten:
    2
    Aufrufe:
    970
  4. Antworten:
    1
    Aufrufe:
    1.094
  5. Antworten:
    1
    Aufrufe:
    1.975