#include <iostream>
#include <string>
#include <ctime>
#include <cmath>
using namespace std;

//*******************************************************************************************************************
struct node;

int fsm(char *tab, int size);
void add_values_to_fsm(int **fsm, bool in_a_row);
int rabin(int *wz, int size);
int count_modulo(int *array, int size, int from);

//*******************************************************************************************************************

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
                                                                                                   //struktura danych
struct node
{
	string imie;
	double pesel;
	node* next;

	void dodaj(string im, double pes, node *&wpis);
	void wyswietl(string im, node *tmp);
};

//***********************************************************************
                                             //funkcje skladowe struktury
void node::dodaj(string im, double pes, node *&wpis)
{
	node *tmp = new node;
	tmp->imie = im;
	tmp->pesel = pes;
	tmp->next = wpis;
	wpis = tmp;
}

//***********************************************************************

void node::wyswietl(string im, node *tmp)
{
	while (tmp->imie != im)
		tmp = tmp->next;

	cout << "Imie: " << tmp->imie << endl
		<< "Pesel: " << tmp->pesel << endl;
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//*******************************************************************************************************************
                                                                                                               //main
int main()
{
	srand(time(NULL));
	char *signs = NULL;
	string imie;
	int ilosc_osob, pozycja, hit_ratio;
	double pesel;
	cout << "Podaj liczbe osob ";
	cin >> ilosc_osob;
	node **Dane = new node*[ilosc_osob];
	for (int i = 0; i < ilosc_osob; i++)
		Dane[i] = NULL;

	int wybor;
	do
	{
		cout << "1. Dodaj nowa osobe" << endl
			<< "2. Odczytaj dane osoby" << endl
			<< "3. Szukanie wzorca automat skonczony" << endl
			<< "4. Rabin"  << endl
			<< "0. Wyjscie" << endl;

		cin >> wybor;
		switch (wybor)
		{
			case 1:
				cout << "Podaj imie osoby ";
				cin >> imie;
				cout << "Podaj pesel osoby ";
				cin >> pesel;
				pozycja = 0;
				for (int i = 0; i < imie.length(); i++)
					pozycja += (int)imie[i];

				pozycja %= ilosc_osob;
				Dane[pozycja]->dodaj(imie, pesel, Dane[pozycja]);
				break;

			case 2:
				cout << "Podaj imie osoby ktora chcesz znalesc ";
				cin >> imie;
				pozycja = 0;
				for (int i = 0; i < imie.length(); i++)
					pozycja += (int)imie[i];

				pozycja %= ilosc_osob;

				Dane[pozycja]->wyswietl(imie, Dane[pozycja]);
				break;

			case 3:
				cout << "Podaj rozmiar tablicy znakow: ";
				int size;
				cin >> size;

				signs = new char[size];

				for (int i = 0; i < size; i++)
					signs[i] = rand()%25+97;

				hit_ratio = fsm(signs, size);
				cout << "Ilosc trafien wynosi: " << hit_ratio << endl;
				break;

			case 4:
				cout << "Podaj dlugosc wzorca ktory chcesz wyszukac: ";
				int dlugosc;
				cin >> dlugosc;
				int *wz = new int[dlugosc];
				for (int i = 0; i < dlugosc; i++)
				{
					cout << "Podaj " << i << " cyfre wzorca: ";
					cin >> wz[i];
				}

				int hits = rabin(wz, dlugosc);
				cout << "Ilosc trafien wynosi: " << hits << endl;
				break;
		}

	} while (wybor != 0);

	return 0;
}

//*******************************************************************************************************************
                                                                  //FSM flying spaghetti monster finite state machine
int fsm(char *tab, int size)
{
	string pattern = "";
	cout << "Podaj wzorzec ktory chcesz wyszukac: ";
	cin >> pattern;

	int **fsm = new int *[3];
	for (int i = 0; i < 3; i++)
		fsm[i] = new int[size + 1];

	int j = 0;

	for (int i = 0; i < size; i++)
	{
		if (tab[i] == pattern[j])
			add_values_to_fsm(fsm, true);


	}

	return 0;
}

//***********************************************************************

void add_values_to_fsm(int **fsm, bool in_a_row)
{

}

//*******************************************************************************************************************
                                                                                                         //rabin-karp
int rabin(int *wz, int size)
{
	int hits = 0;
	bool check = false;
	int wz_mod_digit = 0;
	int rozmiar; //17
	cout << "Podaj rozmiar wzorca: ";
	cin >> rozmiar;
	int *text = new int[rozmiar];
	int *modulo_results = new int[rozmiar];

	for (int i = 0; i < rozmiar; i++)
		modulo_results[i] = -1;

	/*int text[17];
	text[0] = 2;
	text[1] = 3;
	text[2] = 5;
	text[3] = 9;
	text[4] = 0;
	text[5] = 2;
	text[6] = 3;
	text[7] = 1;
	text[8] = 4;
	text[9] = 1;
	text[10] = 5;
	text[11] = 2;
	text[12] = 6;
	text[13] = 7;
	text[14] = 3;
	text[15] = 9;
	text[16] =	9;*/

	for (int i = 0; i < rozmiar; i++)
		text[i] = rand()%9;

	wz_mod_digit = count_modulo(wz, size, 0);

	for (int i = 0; i <= (rozmiar - size); i++)
		modulo_results[i] = count_modulo(text, size, i);

	for (int i = 0; i < rozmiar; i++)
	{
		if (wz_mod_digit == modulo_results[i])
		{
			check = false;

			for (int j = 0; j < size; j++, i++)
			{
				if (wz[j] == text[i])
					check = true;

				else
				{
					check = false;
					break;
				}
			}
		}

		if (check == true)
		{
			hits++;
			i--;
		}
	}

	return hits;
}

//***********************************************************************

int count_modulo(int *array, int size, int from)
{
	int digit = 0;

	for (int i = (size - 1 + from), potega = 0; i >= from; i--, potega++)
	{
		 digit += array[i] * (pow(10, potega));
	}

	 digit %= 13;

	 return digit;
}

//*******************************************************************************************************************