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

int dlugosc(char *lan);
int* init_next(char *wzor);
int KMP(char *tekst, char *wzor, int *next); 
int BM(char *tekst, char *wzor); 
int main()
{ char *tekst="ABCDEFGH"; 
	char *wzor = "FGH"; 
	int *next;
	int cos;
	next = init_next(wzor);
	printf("%in", KMP(tekst,wzor,next));
	printf("%in", BM(tekst,wzor));
	system("PAUSE");

}
int dlugosc(char *lan)
{
	int i;
	for(i=0; lan[i] != '�';i++){}
	return i;
}
int* init_next(char *wzor)
{
	int i,j;
	int M = dlugosc(wzor);
	int *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; 
}
void init_shift(char *wzor, int *shift)
{int i; 
int K=256;
int M=dlugosc(wzor);
for(i=0;i<K;i++)
	{
		shift[i]=M;
	}
for(i=0;i<M;i++)
	{
		shift[wzor[i]]=M-i-1;
	
	}
}
int KMP(char *tekst, char *wzor, int *next)
{ 
	int i,j;
	int N=dlugosc(tekst); 
	int 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 i,j,x,shift[256];
  int M = dlugosc(wzor); 
  int N = dlugosc(tekst);
  init_shift(wzor,shift); 
  for(i = M-1, 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 -1;
		j=M-1;
	  }
  return i+1;
 }