+ Auf Thema antworten
Zeige Ergebnis 1 bis 2 von 2

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

  1. #1
    Don Szene gruen gruen gruen gruen 
    Registriert seit
    Nov 2011
    Beiträge
    155
    Thumbs Up
    26 | 12
    Points: 2.447, Level: 11
    Level completed: 50%, Points required for next Level: 203
    Overall activity: 0%

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

    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

    0 Not allowed!
    Keine Gewalt ist auch keine Lösung.

  2. #2
    The Madness blau blau  Benutzerbild von ChillingStream
    Registriert seit
    Oct 2004
    Ort
    Castle Wolfenstein
    Beiträge
    2.869
    Thumbs Up
    13 | 0
    Points: 6.127, Level: 18
    Level completed: 63%, Points required for next Level: 223
    Overall activity: 0%
    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

    0 Not allowed!


Ähnliche Themen

  1. [C/C++] Präfix/Postfix C
    Von Romka im Forum Programmierung & Entwicklung
    Antworten: 2
    Letzter Beitrag: 07.07.2010, 17:27

Stichworte

Forumregeln

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •