#include <stdio.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 *KMP_w(char *tekst, char *wzor, int *next, int *ilosc);
int *BM_w(char *tekst, char *wzor, int *ilosc);

main()
{
    char wzor[20], tekst[200];
    int i, N, M, ilosc=0, *next, *indeksy, pos=0;
    indeksy=NULL;

    while (pos!=-1)
    {
        printf("\n----K M P----\n");
        printf("\nPodaj tekst:");
        gets(tekst);
        printf("\nPodaj wzorzec:");
        fflush(stdin);
        gets(wzor);
        //N=dlugosc(tekst);
        //M=dlugosc(wzor);
        next=init_next(wzor);
        pos=KMP(tekst, wzor, next);
        if (pos>=0)
        {
            printf("\nZnaleziono wzorzec na pozycji: %d", pos);
            indeksy=KMP_w(tekst, wzor, next, &ilosc);
            printf("\nIlosc powtorzen wzorca: %d", ilosc);
            printf("\nna pozycjach: \n");
            for (i=0; i<ilosc; i++)
                printf("%d; ", *(indeksy+i));
        }
        else
            printf("\nNie znaleziono wzorca w tekscie\n");
        getch();
    }
    pos = 0;
    while (pos!=-1)
    {
        printf("\n----B M----\n");
        printf("\nPodaj tekst:");
        gets(tekst);
        printf("\nPodaj wzorzec:");
        fflush(stdin);
        gets(wzor);
        //N=dlugosc(tekst);
        //M=dlugosc(wzor);
        pos=BM(tekst, wzor);
        if (pos>=0)
        {
            printf("\nZnaleziono wzorzec na pozycji: %d", pos);
            indeksy=BM_w(tekst, wzor, &ilosc);
            printf("\nIlosc powtorzen wzorca: %d", ilosc);
            printf("\nna pozycjach: \n");
            for (i=0; i<ilosc; i++)
                printf("%d; ", *(indeksy+i));
        }
        else
            printf("\nNie znaleziono wzorca w tekscie\n");
        getch();
    }
}

int dlugosc(char *lan)
{
    int i=0;
    while(*(lan+i)!='\0') i++;
    return i;
}

int *init_next(char *wzor)
{
    int i, j;
    int M=dlugosc(wzor);
    int *next;
    next = malloc(M*sizeof(int));
    *next=-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;
}

void init_shift(char *w, int *shift)
{
    int i, K=256, 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, N=dlugosc(tekst), 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 shift[256], M=dlugosc(wzor), N=dlugosc(tekst), x, i, j;
    for (i=M-1, j=M-i; 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;
}

int *KMP_w(char *tekst, char *wzor, int *next, int *ilosc)
{
    int i=0, j, N=dlugosc(tekst), M=dlugosc(wzor), k=0;
    int *indeksy;
    indeksy=NULL;
    *ilosc =0;
    while (k<N)
    {
        for (i=k, j=0; i<N && j<M; i++, j++)
            while ((j>=0)&&(tekst[i] != wzor[j]))
                j=next[j];
        if(j==M)
        {
            indeksy = (int*)realloc(indeksy, (*ilosc+1)*sizeof(int));
            *(indeksy+ *ilosc)=i-M;
            (*ilosc)+=1;;
        }
        k=i;
    }
    return indeksy;
}

int *BM_w(char *tekst, char *wzor, int *ilosc)
{
    int shift[256], N=dlugosc(tekst), M=dlugosc(wzor), x, i, j, k;
    int *indeksy=NULL;
    init_shift(wzor, shift);
    *ilosc=0;
    k=M-1;
    while(k<N)
    {
        for (i=k, 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 indeksy;
                j=M-1;
            }
            *ilosc+=1;
            indeksy=(int*)realloc(indeksy, (*ilosc)*sizeof(int));
            *(indeksy+(*ilosc)-1)=i+1;
            k=i-j+M;
    }
    return indeksy;
}