AiSD Lab 2 - dokonczyc

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

int dlugosc (char *lan);
int * init_next(char *wzor);
void init_shift(char *w, int*shift);
int KMP(char *tekst, char *wzor, int *next);
int BM (char *tekst, char *wzor);
int main(){
    /* TEST funkci dlugosc
    int dl;
    dl = dlugosc("ala11");
    printf("dL: %i", dl); */

    int  *next, i, dlWzorca, kmpTEST, bmTEST;
    //char wzor[256];
    char wzor[]= "ABACABAB";
    dlWzorca = dlugosc( wzor);
    next = init_next(wzor);

    for(i=0; i< dlWzorca; i++)
        printf("\n[ %i ] = %i", i, next [i]);

    kmpTEST = KMP("BABABAABBABAABBB",  "BABAABBB",  init_next("BABAABBB") );
    if(kmpTEST == -1) printf("\nNie znaleziono!");
    else printf("\nZnaleziono na: %i", kmpTEST);

    bmTEST = BM("BABABAABBABAABBB",  "BABAABBB");
    if(bmTEST == -1) printf("\nNie znaleziono!");
    else printf("\nZnaleziono na: %i", bmTEST );

    system("pause");
    return 0;
}

int dlugosc (char *lan)
{
    int i;
    for(i=0; i<256; i++)
        if(lan[i] =='\0') break;

    return i;
}
// to jest do KMP
int *init_next(char *wzor){
    int M = dlugosc(wzor);
    int *next = malloc(M*sizeof(int)); // M to dlugosc wzorca,
    int i ; // indeks tekstu
    int j; // indeks wzoraca
    next[0] = -1;


    for(i=0, j=-1; i<M-1; i++, j++, next[i]=j)
        while( (j>=0) && (wzor[i] != wzor[j]) )
            j = next[j];
    return next;
}
//  to jest do BM
void init_shift(char *w, int*shift){

    int i;
    int K = 256;
    int M = dlugosc(w);

    for(i=0; i<K; i++)
        shift[i] = M;
    for(i=0; i<M; i++)
        shift[ w[i] ] = M-i-1;
}

int KMP(char *tekst, char *wzor, int *next)
{
    int i, j;
    int N = dlugosc(tekst);
    int M = dlugosc( wzor);
    for(i=0, j=0; i<N &&j<M; i++, j++)
        while (( j>=0) && (tekst[i] != wzor[j]))
            j = next[j];

    if(j == M)
        return i-M;
    else
        return -1;
}

int BM (char *tekst, char *wzor)
{
    int i, j;
    int M = dlugosc(wzor);
    int N = dlugosc(tekst);
    int shift [256];
    int x;
    init_shift(wzor, shift);

    for(i=M-1, j=M-1; j>=0; i--, j--)
    {
        while(tekst[i] != wzor[j]) {
            x = shift[tekst[i]];
            if(M-j > x)
                i += M-j;
            else i += x;

            if(i >= N)
                return -1;

            j = M-1;
        }
    }

    return i+1;
}