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


long cmps=0;

int bruteforce(char* text, char* subst)
{
    int tlen=strlen(text);
    int flen=strlen(subst);
    cmps=0;
    for (int i=0; i<(tlen-flen); i++)
    {
	cmps++;
	int k=0;
	while (k<flen && (subst[k]=='.' || text[i+k]==subst[k]))
	{
	    cmps++;
	    k++;
	}
	if (k==flen)
	{
	    return i;
	}
    }
    return -1;
}


char* readfile(char* filename)
{
    int siz=0;
    int sizInc=200;
    FILE* f = fopen(filename, "r");
    char* cc = NULL;
    char* dd;
    char ch;
    int ccount=0;
    while (EOF!=(ch=fgetc(f)))
    {
	if (ccount>siz-1)
	{
	    siz += sizInc;
	    cc = realloc(cc, siz);
	}
	dd=&(cc[ccount]);
	*dd = ch;
	dd++;
	ccount++;
	    //cc[ccount++]=ch;
    }
    cc[ccount]='\0';
    printf("read %d chars  (%d)\n", ccount, strlen(cc));
    return cc;
}

int boyermoore(char* text, char* subst)
{
    int map[128] = {-1};
    int tlen=strlen(text);
    int flen=strlen(subst);
    for (int i=0; i<flen; i++)
    {
	map[subst[i]]=i;
    }
    #ifdef DEBUG
    for (int i=0; i<128; i++)
    {
	if (map[i]>0)
	    printf("BM last %c %d\n", i, map[i]);
    }
    #endif
    int i=flen-1;
    int k=flen-1;
    cmps=0;
    while (i < tlen)
    {
	cmps++;
	if (subst[k]=='.' || text[i]==subst[k])
	{
	    if (k==0) {
		return i;
	    }
	    i--;
	    k--;
	}
	else
	{
	    i += flen - (k<(1+map[text[i]]) ? k : (1+map[text[i]]));
	    k = flen-1;
	}
    }
    return -1;
}

int* buildfail(char* subst)
{
    int flen=strlen(subst);
    
    int* fail = malloc(flen*sizeof(int));
    int j=1;
    int k=0;
    for (int i=0; i<flen; i++) fail[i]=0;
    while (j<flen)
    {
	if (subst[j]==subst[k])
	{
	    fail[j]=k+1;
	    j++;
	    k++;
	}
	else if (k>0)
	{
	    k=fail[k-1];
	}
	else
	{
	    j++;
	}
    }
    #ifdef DEBUG
    for (int i=0; i<flen; i++)	printf("fail %d %d\n", i, fail[i]);
    #endif
    return fail;
}

int kmp(char* text, char* subst)
{
    int tlen=strlen(text);
    int flen=strlen(subst);
    if (flen==0) return -1;
    int* fail = buildfail(subst);
    int j=0;
    int k=0;
    cmps=0;
    while (j < tlen)
    {
	cmps++;
	if (text[j]==subst[k])
	{
	    if (k==(flen-1))
	    {
		free(fail);
		return j-flen+1;
	    }
	    j++;
	    k++;
	}
	else if (k>0)
	{
	    k=fail[k-1];
	}
	else
	{
	    j++;
	}
    }
    free(fail);
    return -1;
}



int main(int argc, char* argv[])
{
    char* text = readfile(argv[1]);
    char* subst = argv[2];

    int ii = bruteforce(text, subst);
    if (ii>=0)
    {
	printf("MM  Found at %d  %d ", ii, cmps);
	for (int j=0; j<strlen(subst); j++) printf("%c", text[ii+j]);
	printf("\n");
    }
    else
	printf("BR  Not found %d\n", cmps);

    ii=boyermoore(text, subst);
    if (ii>=0)
    {
	printf("BM  Found at %d  %d ", ii, cmps);
	for (int j=0; j<strlen(subst); j++) printf("%c", text[ii+j]);
	printf("\n");
    }
    else
	printf("BM  Not found %d\n", cmps);

    ii=kmp(text, subst);
    if (ii>=0)
    {
	printf("KMP Found at %d  %d ", ii, cmps);
	for (int j=0; j<strlen(subst); j++) printf("%c", text[ii+j]);
	printf("\n");
    }
    else
	printf("KMP Not found  %d\n", cmps);

    free(text);
}