gistfile1.h

/* 
 * File:   main.c
 * Author: lite
 *
 * Created on 15 marzec 2010, 22:19
 */

#define EXIT_FAIL 10

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * 
 */
int main(int argc, char** argv) {

    /* Sprawdzenie czy podano wzorzec i tekst */
    if(argc != 3)
    {
        printf("Blad argumentow\n %d", argc);
        return (EXIT_FAIL);
    }

    /* Obliczenie dlugosci tekstu */
    int dlugosc_tekstu = strlen(argv[2]);
    /* Etykietowanie? */
    char* tekst = argv[2];

    printf("%s\n", tekst);

    char *wzorzec = argv[1];
    int dlugosc_wzorca = strlen(wzorzec);

    /* Alokacja pamieci dla tablicy przesuniec */
    int* KMPNext = (int*) malloc(sizeof(int) * dlugosc_wzorca+1);
    int b, i;

    /* Nadanie wartosci poczatkowych
     *  Wstawienie wartownika -1
     * Dlugosc prefikso-sufiksu na -1 */
    KMPNext[0] = -1;
    b = -1;

    /*
     * Stworzenie tablicy dla wzorca
     * Wyznaczamy wartosci prefikso-sufiksow
     */
    for(i=1; i<=dlugosc_wzorca; i++)
    {
        /*
         * Wychodzimy jak trafimy na wartownika
         * albo prefikso-sufiks jest rozszerzalny
         */
        while (b > -1 && wzorzec[b] != wzorzec[i - 1])
        {
            b = KMPNext[b];
        }

        /* Rozszerzamy prefikso-sufisk */
        ++b;

        /*
         * Jeśli następny znak wzorca różni się od znaku tuż za prefikso-sufiksem
         * to w tablicy KMPNext[ ] umieszczamy szerokość prefikso-sufiksu. Inaczej w
         * KMPNext umieszczany zredukowaną szerokość prefikso-sufiksu
        */
            if((i = dlugosc_wzorca) || (wzorzec[i] != wzorzec[b]))
                KMPNext[i] = b;
            else
                KMPNext[i] = KMPNext[b];
    }

    /* Wstępna pozycja wzorca */
    int pp = 0;
    /* Wstępna dlugosc prefikso-sufiksu */
    b = 0;

    for(i=0; i<=dlugosc_tekstu; i++)
    {
        while(b > -1 && (wzorzec[b] != tekst[i]))
        {
            b = KMPNext[b];
        }

     if(++b == dlugosc_wzorca)
        {
          while(pp < i - b + 1)
          {
            printf(" ");
            pp++;
          }
             printf("^");
             pp++;

             b = KMPNext[b];
        }

        }

        printf("\n");
        return (EXIT_SUCCESS);
    }