wyszukiwanie wzorca w tekscie... ;/

#include <iostream>
#include <fstream>
#include <cstring>
#include <string>
#include <conio.h>
#include <cstdlib>
#include <vector>
#include <cmath>

using namespace std;

ifstream wej;
int poz;
vector <string>tekst;
vector <string>wzorzec;

void pobierz_tekst();
void pobierz_wzorzec();
//void Brute_Force();
void Rabin_Karp();
int h(int wiersz);

unsigned licznikBF, licznikRK;

const long p = 33554393;
int d;

int main()
{
    pobierz_tekst();
    pobierz_wzorzec();
    //Brute_Force();
    //cout<<"\nRabin-Karp\n\n";
    Rabin_Karp();
    getch();
    return 0;
}

/**FUNKCJA POBIERAJACA Z PLIKU TEKST KTORY BEDZIE PRZESZUKIWANY**/
void pobierz_tekst()
{
    wej.open("tekst.txt",ios::in);

    while(!wej.eof())
    {
        string zmienna1;
        getline(wej,zmienna1);
        tekst.push_back(zmienna1);
    }

    wej.close();
	
	cout<<"Tekst\n" << endl;
    for(int i=0; i<tekst.size(); i++)
    {
        cout<<tekst[i]<<endl;
    }

      cout<<endl<<"Tekst ma wymiary "<<tekst.size()<<" x "<<tekst[0].size()<<endl;

}

/**FUNKCJA POBIERAJACA Z PLIKU WZOR**/
void pobierz_wzorzec()
{
    wej.open("wzorzec.txt",ios::in);

    while(!wej.eof())
    {
        string zmienna;
        getline(wej,zmienna);
        wzorzec.push_back(zmienna);
    }

    wej.close();

    cout<<"\n\nWzorzec:\n" << endl;
    for(int i=0; i<wzorzec.size();i++)
    {
        cout<<wzorzec[i]<<endl;
    }
    cout<<endl<<"Wzor ma wymiary "<<wzorzec.size()<<" x "<<wzorzec[0].size()<<endl;
}

void Brute_Force()
{

	int m= tekst.size();
	int n= wzorzec.size();
	int l,i,j;
	int wiersz_tekstu=0;
	int wiersz_wzorca=0;

	for(i = 0; i < m-n-1 ;i++) //ustawienie zakresu po ktorym bedziemy operowac
	{
		for(int wiersz_tekstu=0; wiersz_tekstu < m; wiersz_tekstu++) //przechodzenia po wierszach
		{
			for(wiersz_wzorca=0; wiersz_wzorca < n;wiersz_wzorca++)
			{
				for (j =0; j < n; j++) // przechodzenie po literach
				{
					if(tekst[wiersz_tekstu][j+i]==wzorzec[wiersz_wzorca][j])
					{
						l++;
					}
					else
					{

						break;
					}
				   if(j==n)
				   {	
						cout<<"Znaleziono zgodnosc na pozycji: "<<tekst[i]<<endl;
				   }

				}
				
				
			}
		}
		
	}
}

void Rabin_Karp()
{
       unsigned M,N,h,P=0,T=0, TempT, TempP;
       int i,j,k,poz=0;
       M = wzorzec[0].size();
       N = tekst[0].size();
       h = (int)pow(d,M-1) % p; /**Kolejna potega liczby pozycji**/


        int wiersz_tekstu=0;
        int wiersz_wzorca=0;

        licznikRK=0;

/**==================================Obliczanie hasha dla wzorca P, oraz tekstu T======================================================**/
               for(i=0;i<M;i++){
                    P = ((d*P) + (int)wzorzec[wiersz_wzorca][i]); //% p;/**d- jest iloscia lier alfabetu, p- liczba pierwsza**/
                }
/**================================================PRZESZUKIWANIE TEKSTU W POSZUKIWANIU WZORCA========================================**/
/**===================================================================================================================================**/


for(int wt=0; wt<tekst.size()-1;wt++)
{
    for(i=0;i<M;i++)
    {
       TempT = ((d*T) + ((int)tekst[wt][i]));
       T =  TempT;
    }if(T<0){T=T*(-1);}


                for(i=0;i<=N-M;i++)/**przechodzenie po literach**/
                    {
                        /**Jezeli kod wzorca jest taki sam jak kod tekstu to prawdopodobnie mamy szukany podciag**/
                            if(P==T){
                                   for(k=1;k<wzorzec.size();k++)/**jezeli hash dla pierwszych wierszy pasuje to sprawdzamy litery w pozostalych k-1 wierszach w dol**/
                                        {
                                         for(j=0;j<M;j++)/**sprawdzanie kolejnych liter okienku nalozonym na tekst (tak samo jak Brute Force)**/
                                               {
                                                licznikRK++;
                                                if(tekst[wt+k][i+j] != wzorzec[wiersz_wzorca+k][j]){break;}/**Jezeli litery wzorca i tekstu nie zgadzaja sie to przerwyamy**/
                                               }
                                               /**Petla koncz sie na pierwszym niezgodnym znaku tak wiec dalej
                                                przekazywana jest pozycja ostatniego zgodnego znaku i jezeli j wynosi tyle samo co dlugosc wzorca tzn ze mamy zgodnosc
                                                bo j liter bylo takich samych co litery wzorca**/

                                                    if((j == M) && (k==wzorzec.size()-1))/**Jezeli ilosc zgodnych liter jest rowna wielkosci wzorca
                                                                                i odnosi sie to do kazdej lini wzorca to znalezlismy szukany wzorzec**/
                                                       {
                                                        //cout<<"\nZnaleziono wzor na pozycji:  "<< wt+1<<" "<<i+1<<"\n"
                                                          //  <<"Ostatni wiersz pasujacy do wzorca na pozycji "<<wt+k+1<<" "<<i+1<<"\n";
                                                       }

                                        }

                                    }
                                     TempT =((d*(T - tekst[wt][i]*h)) + ((int)tekst[wt][i+M]));/**Wyliczanie nowego hasha dla tekstu**/
                                     T = TempT;/**Wykonanie operacji modulo na nowo wyliczonym hashu Tekstu**/
                                     if(T<0){T=T*(-1);}

                    }
                    T=0;

/**===================================================================================================================================**/
    }/**KONIEC PIETLI FOR NA ROZSZERZENIE WIERSZY**/
    cout<<"\nRabin-Karp ilosc porownan: "<<licznikRK<<endl;
}