#include <iostream>
#include <string.h>

using namespace std;
const int n = 29;

typedef struct slownik
{
	struct slownik *tablica[n];
} USS, *USS_PTR;

int do_indeksu(char znaki)
{
	if ((znaki <= 'Z') && (znaki >= 'A') || (znaki <= 'z') && (znaki >= 'a'))
	{
		return toupper(znaki) - 'A';
	}
	else
	{
		if (znaki == ' ')
		{
			return 26;
		}
		if (znaki == '-')
		{
			return 27;
		}
	}
}

char z_indeksu(int n)
{
	if ((n >= 0) && (n <= ('Z' - 'A')))
	{
		return toupper((char) n + 'A');
	}
	else
	{
		if (n == 26)
		{
			return ' ';
		}
		if (n == 27)
		{
			return '-';
		}
	}
}

void zapisz(char *slowo, USS_PTR p)
{
	USS_PTR q;
	int pos;
	for (int i = 1; i <= strlen(slowo); i++)
	{
		pos = do_indeksu(slowo[i - 1]);
		if (p->tablica[pos] != NULL)
		{
			p = p->tablica[pos];
		}
		else
		{
			q = new USS;
			p->tablica[pos] = q;
			for (int j = 0; j < n; q->tablica[j++] = NULL)
			{
				p = q;
			}
		}
	}
	p->tablica[n - 1] = p;
}

void pisz_slownik(USS_PTR p)
{
	for (int i = 0; i < 26; i++)
	{
		if (p->tablica[i] != NULL)
		{
			if ((p->tablica[i])->tablica[n - 1] == p->tablica[i])
			{
				cout << z_indeksu(i) << endl << " ";
			}
			else
			{
				cout << z_indeksu(i);
				cout << "-";
				pisz_slownik(p->tablica[i]);
			}
		}
	}
}

void szukaj(char slowo[], USS_PTR p)
{
	int test = 1;
	int i = 0;
	while ((test == 1) && (i < strlen(slowo)))
	{
		if (p->tablica[do_indeksu(slowo[i])] == NULL)
		{
			test = 0;
		}
		else
		{
			p = p->tablica[do_indeksu(slowo[i++])];
		}
        if ((i == strlen(slowo)) && (p->tablica[n - 1] == p) && test)
        {
            cout << "Slowo znalezione!\n";
            return;
        }
	}
	cout << "Slowo nie zostalo znalezione!\n";
}

int main()
{
	int i;
	char tresc[50];

	USS_PTR p = new USS;

	for (i = 0; i < n; p->tablica[i++] = NULL);
    for (i = 1; i <= 3; i++)
		{
			cout << "Podaj slowo, ktore trzeba umiescic w slowniku: ";
			cin >> tresc;
			zapisz(tresc, p);
		}
        pisz_slownik(p);
        for (i = 1; i <= 3; i++)
        {
            cout << "Podaj slowo, ktore trzeba wyszukac w slowniku: ";
        }
        cin >> tresc;
        szukaj(tresc, p);
	return 0;
}