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

int licznik=0;

int usunznak(char* tekst, int dlugosc){
	int miejsce=0;
	for(int i=0;i<dlugosc;i++){
		if(tekst[i]=='\n'){
			miejsce++;
		}else{
		tekst[miejsce]=tekst[i];
		miejsce++;
		}
	}
	return miejsce;//nowa dlugosc tekstu
}



void Naiwny(char* P,char* T,int m,int n){
	n = usunznak(T,n);
	m = usunznak(P,m);
	// P - wzorzec, tablica [1..m],
	// T - tekst, tablica [1..n],
	for(int s=0;s<n-m;s++){
		for(int i=0;i<m;i++){
			if(T[s+i]!=P[i]){
				break;
			}
			if(i==m-1){
				printf("znaleźliśmy wzorzec na miejscu: %d\n", s);

			}
		}
	}
}

void RabinKarp(char* P,char* T,int d,int q, int m, int n){
// P - wzorzec, tablica [1..m],
// T- tekst, tablica [1..n],
// d - rozmiar alfabetu (np. 128),
// q - liczba pierwsza (np. 27077)
	n = usunznak(T,n);
	m = usunznak(P,m);
	int h=1;
	for(int i=0;i<m-1;i++){
		h = (h*d)%q; // wyliczy h = (d do potęgi m-1) modulo q
	}
	int p=0;
	int t=0;
	for(int i=0;i<m;i++){
		p = (d*p+P[i])%q;
		t = (d*t+T[i])%q;
	}
	// wyliczone: wartość p "kodująca" P[1..m]
	// oraz wartość t "kodująca" T[s+1..s+m] dla s==0
	// kodowanie niejednoznaczne! (haszowanie)
	for(int s=0;s<n-m;s++){
		if(p==t){
			for(int i=0;i<m;i++){
				if(T[s+i]!=P[i]){
					break;
				}
				if(i==m-1){
					printf("znaleźliśmy wzorzec na miejscu: %d\n", s);
				}
			}
		}

		if(s<n-m){ // czy tekst się nie skończył?
			int t1=(T[s+1]*h)%q;
			if(t<t1){
				t=t+q;
			}
			t = (d*(t-t1)+T[s+m+1])%q;
		}
	}
}
// czyli t = (d*(t-T[s+1]*h)+T[s+1+m])%q, gdzie arytmetyka jest
// modulo q (mnożenie i odejmowanie)
// to wylicza wartość t "kodującą" T[s+2, ... , s+m,s+1+m]
// na podstawie wartości t "kodującej" T[s+1,s+2, ... , s+m]


int* PrefixFunction(char*P, int m){
	// P - wzorzec, tablica [1..m]
	int* pi=calloc(m,sizeof(int));
	pi[0]=0;
	int k=0;
	for(int q=1;q<m;q++){
		// mamy: P[1..k]==P[...q-1], k==pi[q-1]
		while(k>0 && P[k] != P[q-1]){
			k=pi[k];
		}
		if(P[k] == P[q-1]){
				k=k+1;
		}
		pi[q]=k;
	}
	return pi;
}


//Wyszukiwanie wzorca
void KMP(char* T,char* P, int n, int m){
	n = usunznak(T,n);
	m = usunznak(P,m);
	// T - tekst, tablica [1..n]
	// P - wzorzec, tablica [1..m]
	int* pi = PrefixFunction(P, m);
	int q=0;
	for(int i=0;i<n;i++){
	// mamy: P[1..q]==T[...i-1]
		while(q>0 && P[q] != T[i]){
			q=pi[q-1];
		}
		if(P[q] == T[i]){
			q=q+1;
		}
		if(q==m){
		printf("znaleźliśmy wzorzec na miejscu: %d\n", i-m+1);
		q=pi[q-1];
		}
	}
}
int wczytaj(FILE* fileptr, char** buffer)
{
    char a;
    int C=0;
    long filelen;

    fseek(fileptr, 0, SEEK_END);          // Jump to the end of the file
    filelen = ftell(fileptr);             // Get the current byte offset in the file
    rewind(fileptr);                      // Jump back to the beginning of the file

    *buffer = (char *)malloc((filelen+1)*sizeof(char)); // Enough memory for file + \0
    fread(*buffer, filelen, 1, fileptr); // Read in the entire file
    fclose(fileptr); // Close the file
    return filelen;
}
int main(){
	char* wzorzec;
	char* tekst;

	FILE* f=fopen("wzorzec.txt", "r");
	int dlugoscw = wczytaj(f, &wzorzec);
	FILE* f2=fopen("tekst.txt", "r");
	int dlugosct = wczytaj(f2, &tekst);

	//Naiwny(wzorzec,tekst,dlugoscw, dlugosct);
	//RabinKarp(wzorzec,tekst,128,27077,dlugoscw, dlugosct);
	KMP(tekst,wzorzec,dlugosct, dlugoscw);





}