//Algorytm KMP
//wykonal Grzegorz Gasiewski 
//pobrano ze strony http://gege01.prv.pl

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

#define MAX 50
int Tab[MAX];

int main()
{
int z, //jaka ilosc znakow wzorca jest identyczna ze znakami tekstu
    i, //licznik glowny
    p, //licznik wykorzystowany przy kolorowaniu liter
    kmp, //sprawdza czy znaleziono wzorzec
    n, //wykorzystywana przy komentarzu
    m; //wykorzystywana przy komentarzu

char wzorzec[MAX]={'P'}, //wzorzec; zapelniony po to zerowa komorke, by
			//zaczynac petle od 1
     tekst[MAX], //tekst
     tab_pom[MAX]; //tablica pomocnicza; wykorzystywana po to, by
		  // zaczynac petle od 1


void f_prefiksowa(char wzorzec[]); // funkcja prefiksowa

//*************** strona tytulowa *******************
clrscr();
printf("\nGRZEGORZ GASIEWSKI  gr. 203 IDM 'A'\n\n\n\n\n\n");
printf("TEMAT:\n\nDemonstracja sortowania Knutha-Morris-Pratta.\n");
printf("\nProgram edukacyjny demonstruje krok po kroku sposob dzialania algorytmu\n");
printf("\nKnutta-Morris-Pratta.");

gotoxy(64,50);
printf("Nacisnij <ENTER>");

getchar();
//*************** koniec strony tytulowej ****************


//***** wpisywanie tekstu i wzorca oraz opis funkcji prefiksowej ***
clrscr();

printf("\nPodaj tekst i nacicisnij <ENTER>: ");
gets(tekst);

printf("\nPodaj wzorzec i nacisnij <ENTER>: ");
gets(tab_pom);


strcat(wzorzec,tab_pom); //robione po to by wzorzec zaczynal sie od 1

printf("\n\n\n\n\n\n\nAlgorytm Knutha-Morissa-Patha zaczyna sie od wyznaczenia funkcji prefiksowej.\n\n\n\n");

printf("     *** WYZNACZANIE FUNKCJI PREFIKSOWEJ DLA WZORCA ***\n\n");
printf("Ustalamy sobie zmienna np. 'k', ktora na poczatku ma wartosc = 0 oraz tablice o dlugosci = dlugosci wzorca.\n");
printf("Bedziemy wykonywac 'i' iteracji, gdzie i=dlugosc wzorca.\n");
printf("W i-tej komorce tablicy bedzie wpisana wartosc maksymalnego prefiksu wzorca,\n");
printf("ktory jest rownoczesnie jego sufiksem.");
printf(" Jest to wartosc, ktora pokazuje nam o ilepol nalezy przesunac sie we wzorcu.\n");
printf("Do pierwszej komorki tablicy wpisujemy 0. Nastepnie wykonujemy tyle iteracji,\n");
printf("jak dlugi jest wzorzec.\n");
printf("W kazdej iteracji porowujemy 'k-ty' element z elementem 'i-tym'.\n\n");
printf("Jesli oba elementy sa identyczne, to zwiekszamy zmienna 'k' o 1 i wpisujemy\n");
printf("ja do 'i-tej' komorki tablicy.\n\n");
printf("Jesli te dwa elementy sa rozne, to do 'i-tej' komorki tablicy wpisujemy wartosc 'k'.\n\n");
printf("Jesli wartosc 'k'>0 i oba elementy sa rozne, to zmienna 'k' przyjmuje wartosc z\n");
printf("'k'-tej komorki tablicy. Czynnosc ta wykonuje sie az do momentu, gdy 'k'<=0 lub\n");
printf("oba elementy beda identyczne.");

gotoxy(64,50);
printf("Nacisnij <ENTER>");

getchar();
//**** koniec wpisywania tekstu i wzorca oraz opisu funkcji prefiksowej ***


//***** wyswietlenie pierwszego elementu tablicy oraz wartosci 'z' ***
clrscr();

printf("\nWzorzec: ");
	for(i=1;i<=strlen(wzorzec)-1;i++)
	printf("%c",wzorzec[i]);
printf("\n\n\n\n");

printf("Tablica[1]=0\n\n");
printf("k=0");

gotoxy(64,50);
printf("Nacisnij <ENTER>");
//*** koniec wyswietlenia pierwszego elementu tablicy oraz wartosci 'z' ***


// ***** dzialanie funkcji prefiksowej ****
f_prefiksowa(wzorzec);
// ***** koniec dzialania funkcji prefiksowej ****

// **** opis dzialania algorytmu KSM ****
clrscr();

printf("\n\n\n\n\nPo wyliczeniu tablicy wyszukanie wzorca mozna rozwiazac za pomoca algorytmu KSM.\n\n\n");
printf("\n\n\n\n         ---  Algorytm KSM ---\n\n");
printf("Ustalamy sobie zmienna np. 'z', ktora na poczatku ma wartosc = 0.\n");
printf("Bedziemy wykonywac 'i' iteracji, gdzie i=dlugosc tekstu.\n");
printf("W kazdej iteracji porownujemy 'z'-ty element wzorca z 'k'-tym elementem tekstu.\n");
printf("Jesli te dwa elementy beda identyczne, to zwiekszamy wartosc z o 1.\n");
printf("Jesli wartosc 'z'>0 i oba elementy sa rozne, to zmienna 'z' przyjmuje wartosc z\n");
printf("'z'-tej komorki tablicy. Czynnosc ta wykonuje sie az do momentu, gdy 'z'<=0 lub\n");
printf("oba elementy beda identyczne.\n\n");
printf("Gdy 'z'='dlugosci wzorca', to oznacza, ze znalezlismy wzorzec w tekscie i petla jest przerywana.\n");
printf("Gdy petla jest skonczona, a nie spelniony jest powyzszy warunek, to oznacza, ze wzorzec nie wystepuje w tekscie.");

gotoxy(64,50);
printf("Nacisnij <ENTER>");

getchar();
// **** koniec opisu dzialania algorytmu KSM ****


// ***** wlasciwy algorytm KSM *****
clrscr();

z=0;
kmp=-1;

	for(i=0;i<=strlen(tekst)-1;i++)
	{
	m=n=0;
	      //### podswietlanie literek ###
		printf("\nTekst: ");
			for(p=0;p<=strlen(tekst)-1;p++)
			{
				if(p==(i))  textcolor(12);
				cprintf("%c",tekst[p]);
				normvideo();
			}

		printf("\n\nWzorzec: ");
			for(p=1;p<=strlen(wzorzec)-1;p++)
			{
				if(p==(z+1))  textcolor(11);
				cprintf("%c",wzorzec[p]);
				normvideo();
			}
		//### koniec podswietlania literek ###


	printf("\n\n\n\n-- %d-a iteracja --\n",i+1);

	printf("z=%d\n\n\n",z);

	printf("Porownuje element %d wzorca (z+1) z %d elementem tekstu (i) ('",z+1,i+1);
	textcolor(11);
	cprintf("%c",wzorzec[z+1]);
	normvideo();
	printf("' z '");
	textcolor(12);
	cprintf("%c",tekst[i]);
	normvideo();
	printf("').\n\n\n\n\n");

		while(((z>0)&&(wzorzec[z+1])!=(tekst[i])))
		{
		z=Tab[z];
		n++;
		}

		if(wzorzec[z+1]==tekst[i])
                {
		printf("Porownywane elementy sa identyczne, wiec zwiekszamy 'z' o 1.\n\n\n");
		m=1;
		z++;
		}

		if(n>=1) //### komentarz ###
		{
		printf("Porownywane elementy sa rozne i z>0, wiec zmienna 'z' przyjmuje wartosc\n");
		printf("z 'z'-ej komorki tablicy.\n\n\n");
		printf("Potrzebne byly na to %d 'poditeracje', poniewaz warunkiem zakonczenia 'podpetli'\n",n);
		printf("jest warunek: z<=0  lub  wzorzec[k+1]<>tekst[i].\n\n\n");
		}

		if((m==0)&&(n==0)) //### komentarz ###
		printf("Porownywane elementy sa rozne i z=0, wiec nie zwiekszamy 'z'.\n\n\n");

		printf("z=%d  -  wynika to stad, ze %d pierwszy(e) znak(i) wzorca pasuja do tekstu.\n\n\n",z,z);

		if(z==(strlen(wzorzec)-1))
		{
		kmp=i;
		break;
		}

kmp=-1;

gotoxy(64,50);
printf("Nacisnij <ENTER>");

getchar();
clrscr();
	}
// ***** koniec wlasciwego algorytmu KSM *****


// **** sprawdzenie, czy znaleziono wzorzec w tekscie ****
textcolor(4);

if(kmp<0) cprintf("\n\n\n\nNie znaleziono wzorca w tekscie.");
else cprintf("\n\n\n\n 'z' = dlugosci wzorca   =>   znaleziono wzorzec w tekscie.");

normvideo();

gotoxy(64,50);
printf("Nacisnij <ENTER>");

getchar();
// **** koniec sprawdzenia wzorca w tekscie ****

return 0;
}



void f_prefiksowa(char wzorzec[]) // *** funkcja prefiksowa ***
{
int k, //sprawdza prefiks z sufiksem
    i, //licznik glowny
    h, //licznik wykorzystowany przy kolorowaniu liter
    m, //wykorzystywana przy komentarzu
    n; //wykorzystywana przy komentarzu

Tab[0]=0;
k=0;
	for(i=2;i<=strlen(wzorzec)-1;i++)
	{
	m=n=0;

	getchar();
	clrscr();

	printf("\nWzorzec: ");

		// ### podswietlanie literek ###
		for(h=1;h<=strlen(wzorzec)-1;h++)
		{
		if(h==(k+1))  textcolor(11);
		if(h==(i)) textcolor(12);
		cprintf("%c",wzorzec[h]);
		normvideo();
		}
		// ### koniec podswietlania literek ###

	printf("\n\n\n\n-- %d-a iteracja --\n",i);

	printf("k=%d\n\n\n",k);

	printf("Porownuje element %d (k+1) z elementem %d (i) ('",k+1,i);
	textcolor(11);
	cprintf("%c",wzorzec[k+1]);
	normvideo();
	printf("' z '");
	textcolor(12);
	cprintf("%c",wzorzec[i]);
	normvideo();
	printf("').\n\n\n\n\n");

		while((k>0)&&(wzorzec[k+1]!=wzorzec[i]))
		{
		k=Tab[k];
		n++;
		}

		if(wzorzec[k+1]==wzorzec[i])
		{
		printf("Porownywane elementy sa identyczne, wiec zwiekszamy 'k' o 1.\n\n\n");
		k++;
		m=1;
		}

		if(n>=1) // ### komentarz ###
		{
		printf("Porownywane elementy sa rozne i k>0, wiec zmienna 'k' przyjmuje wartosc\n");
		printf("z 'k'-ej komorki tablicy.\n\n\n");
		printf("Potrzebne byly na to %d 'poditeracje', poniewaz warunkiem zakonczenia 'podpetli'\n",n);
		printf("jest warunek: k<=0  lub  wzorzec[k+1]<>wzorzec[i].\n\n\n");
		}

		if((m==0)&&(n==0)) // ### komentarz ###
		printf("Porownywane elementy sa rozne i k=0, wiec nie zwiekszamy 'k'.\n\n\n");

	printf("k=%d  -  wynika to stad, ze %d pierwsze znaki wzorca (prefiks)\n",k,k);
	printf("        sa rownoczesnie jego koncem (sufiksem).\n\n\n");

	Tab[i]=k;

	printf("Tablica[i]=k   Tablica[%d]=%d\n",i,k);

	printf("\n\n\n\nWartosc poszczegolnych komorek tablicy: ");
		for(h=1;h<=i;h++)
		printf("%d ",Tab[h]);
	}
getchar();
}