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

#ifndef min
    #define min( a, b ) ( ((a) < (b)) ? (a) : (b) )
#endif

int delta_table[1000][1000];
char* slownik = "qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM1234567890";
char *cpy1;
char *cpy2;

int delta(int q, char a){
       int ai = a;
       return delta_table[q][ai-32];
}

int sufix(char* string, char* test){
    int tr = 0;
    int z = 0;
    if(strlen(string)>=strlen(test)){
          for(z=1;z<=strlen(test);z++){
                if(test[strlen(test)-z] == string[strlen(string)-z])
                          tr = 1;
                else{
                     tr = 0;
                     break;
                }
          }
    }
    else
        return tr =0;
    return tr;
}

void ComputeTransitionFunction(char wz[],char slownik[]){
     printf("Wszedlem do CTF!\n");
    int m = strlen(wz);
    int q = 0;
    int j = 0;

    cpy1 = (char*)malloc(sizeof(char)*1000);
    cpy2 = (char*)malloc(sizeof(char)*1000);
    char tmp[] = "";

    for(q=0;q<=m;q++){
        for(j=0;j<strlen(slownik);j++){
                int k = min(m,q+1);
                printf("m = %d, k = %d, q = %d\n",m,k,q);
                printf("wz: %s\n",wz);
                if(q==0){
                         //strncpy(cpy1,wz,k);
                         //strncpy(cpy1,&slownik[j],1);
                         while(sufix(strncpy(cpy2,&slownik[j],1),strncpy(cpy1,wz,k))!=1){
                               printf("Wszedlem\n");
                               printf("WHILE cpy1: %s\n",cpy1);
                               printf("WHILE cpy2: %s\n",cpy2);
                               memset(cpy1, '\0', strlen(cpy1)-1);
                               memset(cpy2, '\0', strlen(cpy2)-1);
                               k=k-1;
                               if(k==0)
                                  break;
                               printf("k = %d\n",k);
                               }
                }
                else{
                         //strncpy(cpy1,wz,k);
                         //strncat(strncpy(cpy2,wz,q),&slownik[j],1);
                         while(sufix(strncat(strncpy(cpy2,wz,q),&slownik[j],1),strncpy(cpy1,wz,k))!=1){
                               printf("Wszedlem\n");
                               printf("WHILE cpy1: %s\n",cpy1);
                               printf("WHILE cpy2: %s\n",cpy2);
                               memset(cpy1, '\0', strlen(cpy1)-1);
                               memset(cpy2, '\0', strlen(cpy2)-1);
                               k=k-1;
                               if(k==0)
                                  break;
                               printf("k = %d\n",k);
                               }
                }
                printf("cpy1: %s\n",cpy1);
                printf("cpy2: %s\n",cpy2);
                //printf("slownik[j] = %s\n",&slownik[j]);
                //printf("strncat = %s\n",strncat(strncpy(cpy2,wz,q),&slownik[j],1));
                //while(sufix(strncat(strncpy(cpy2,wz,q),&slownik[j],1),strncpy(cpy1,wz,k))!=1){

                printf("Przeszedlem\n");
                memset(cpy1, '\0', strlen(cpy1)-1);
                memset(cpy2, '\0', strlen(cpy2)-1);
                printf("Tutaj tez przeszedlem\n");
                int ai = slownik[j];
                delta_table[q][ai-32] = k;
        }
    }
}

void FiniteAutomatonMatcher(char in[], char wz[], int m){
     int n = strlen(in);
     int przesuniecie;
     int q = 0;
     int i = 0;
     printf("Wszedlem do FAM!\n");
     ComputeTransitionFunction(wz,slownik);
     printf("Wrocilem do FAM\n");
     for(i=1;i<=n;i++){
         q = delta(q,in[i]);
         if(q==m){
            przesuniecie = i-m;
            printf("Przesuniecie wzorca: %d\n",przesuniecie);
         }
     }
}

int main(int argc, char *argv[])
{
    char input[1000];
    char wzorzec[1000];
    char wynik[1000];

    printf("Podaj ciag wejsciowy znakow: ");
    scanf("%s",&input);
    printf("Input = %s\n",input);
    printf("\n");
    printf("Podaj wzorzec wyszukowania: ");
    scanf("%s",&wzorzec);
    printf("Wzorzec = %s\n",wzorzec);
    printf("\n");

    int m = strlen(wzorzec);
    FiniteAutomatonMatcher(input,wzorzec,m);

    system("PAUSE");
    return 0;
}