#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
int dlugosc(char*lan);
int* init_next(char*wzor);
int KMP (char* tekst,char* wzor, int* next);

int main()
{

	char wzor[256];
	char tekst[256];
	int* next;
	int M,N,i,j,ind;
	int P[256];//maksymalna dlugosc wzorca to 100 symboli
	printf("Podaj tekst\n");
	fflush(stdin);
	scanf("%255[^\n]s", tekst);
	printf("Podaj wzorzec\n");
	fflush(stdin);
	scanf("%255[^\n]s", wzor);
	N=dlugosc(tekst);
	M=dlugosc(wzor);
	next=init_next(wzor);
	ind=KMP(tekst,wzor,next);
	printf("Indeks poczatku wzorca w tekscie=%d\n",ind);


}


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


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

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;
}