/*
TASK:REG
LANG:C++
*/

#include <fstream>
#include <iostream>

//#define DEBUG

using std::ifstream;
using std::ofstream;
using std::ios;
using std::endl;
using std::cout;

const char dat[] = "reg14.dat";
const char rez[] = "reg14.re";

void pradiniai_duomenys(int &regexpIlgis, char *&regexp, 
						int &eiluteIlgis, char *&eilute)
{
	ifstream f(dat, ios::in);
	f >> regexpIlgis >> eiluteIlgis;
	regexp = new char[regexpIlgis + 1];
	eilute = new char[eiluteIlgis + 1];
	regexp[regexpIlgis] = 0;
	eilute[eiluteIlgis] = 0;
	f.getline(regexp, regexpIlgis);
	f.getline(regexp, regexpIlgis + 1);
	f.getline(eilute, eiluteIlgis + 1);
	f.close();
}

void rezultatai(int ok, int poz)
{
	ofstream f(rez, ios::out);
	if (ok == 1)
		f << "GERAI";
	else
		f << "BLOGAI\n" << poz;
	f.close();
}

// ======================= re.h ========== begin ========================

#define NULL	0

class Vertex;

// grafo briauna
class Edge {
public:
	Edge(int symbol) {
		this->symbol = symbol;
		this->next = NULL;
		this->into = NULL;
	}
	~Edge() {
		//if (next != NULL)
		//	delete next;
		//next = NULL;
	}

	// specialus atvejai: -2 - bet koks simbolis, -1 - epsilon
	int symbol;

	Edge *next;
	Vertex *into;
};

// grafo virsune
class Vertex {
private:
	Vertex(int id) {
		this->id = id;
		this->next = NULL;
		this->links = NULL;
		this->zyme = 0;
		this->regisr_pabaiga = true;
	}
	int id;

public:
	// jeigu naudojame kaip saraso elementa, tai rodo i kita elementa sarase
	Vertex *next;

	// virsunes kaimynai
	Edge *links;

	// naudojama grafo apejime
	int zyme;

	// zymi, ar tai reuliariosios israiskos pabaiga
	bool regisr_pabaiga;

public:
	~Vertex() {
		// atlaisvinam virsunes
		//Vertex *temp = neighb;
		//neighb = NULL;
		//if (temp != NULL) {
		//	delete temp;
		//	// atlaisvinam briaunas
		//	delete edges;
		//}
	}

	static int count;
	static Vertex *NewVertex() {
		Vertex *el = new Vertex(count++);
		return el;
	}

	int Id() {
		return id;
	}

	void AddNeighb(Edge *e, Vertex *v) {
		e->next = links;
		e->into = v;
		links = e;
		regisr_pabaiga = false;
	}

};

class CRe
{
public:
	CRe(int regisr_ilgis, char *regisr);
	~CRe(void);

	Vertex *Saknis() {
		return saknis;
	}

	int ilgis;
	char *regisr;

	bool ok;

private:

	// naudojama nagrinejime
	int poz;
	Vertex *saknis;

	int Simbolis(int kelintas);
	char NuskaitykZenkla();
	char NuskaitykZenkla(char c);
	Vertex *NagrinetiIsraiska(Vertex *&paskutine);
	Vertex *NagrinetiTerma(Vertex *&paskutine);
	Vertex *NagrinetiKartotini(Vertex *&paskutine);
	Vertex *NagrinetiAtoma(Vertex *&paskutine);
	Vertex *NagrinetiZenkla(Vertex *&paskutine);
};

// ======================= re.h ========== end ========================

// ======================= re.cpp ========== begin ========================

CRe::CRe(int regisr_ilgis, char *regisr)
{
	this->ilgis = regisr_ilgis;
	this->regisr = new char[regisr_ilgis];
	for (int i = 0; i < regisr_ilgis; i++)
		this->regisr[i] = regisr[i];

	this->poz = 0;
	this->ok = true;
	Vertex *paskutine = NULL;
	this->saknis = NagrinetiIsraiska(paskutine);
	if (this->poz < regisr_ilgis)
		this->ok = false;
}

CRe::~CRe(void)
{
	if (regisr != NULL)
		delete[] regisr;
	if (saknis != NULL)
		delete saknis;
}

int CRe::Simbolis(int kelintas) {
	if (ok && (poz + kelintas < ilgis)) {
		return regisr[poz + kelintas];
	} else {
		return -1;
	}
}

char CRe::NuskaitykZenkla() {
	int c = Simbolis(0);

	if (c < 0) {
		ok = false;
		return 0;
	}

	++poz;
	return (char) c;
}

char CRe::NuskaitykZenkla(char c) {
	if (c != NuskaitykZenkla()) {
		ok = false;
		return 0;
	}
	return c;
}

Vertex *CRe::NagrinetiIsraiska(Vertex *&paskutine)
{
	Vertex *saknis = Vertex::NewVertex(), *pabaiga = NULL;
	bool pabaiga_sukurta = false;

	saknis->AddNeighb(new Edge(-1), NagrinetiTerma(paskutine));
	pabaiga = paskutine;
	while (Simbolis(0) == '|') {
		if (!pabaiga_sukurta) {
			pabaiga = Vertex::NewVertex();
			paskutine->AddNeighb(new Edge(-1), pabaiga);
			pabaiga_sukurta = true;
		}
		NuskaitykZenkla('|');
		saknis->AddNeighb(new Edge(-1), NagrinetiTerma(paskutine));
		paskutine->AddNeighb(new Edge(-1), pabaiga);
	}
	paskutine = pabaiga;

	return saknis;
}

Vertex *CRe::NagrinetiTerma(Vertex *&paskutine)
{
	Vertex *saknis = Vertex::NewVertex();
	Vertex *paskutinis = saknis;
	bool termas_baigesi = false;

	do {
		Vertex *kartotinis = NagrinetiKartotini(paskutine);
		paskutinis->AddNeighb(new Edge(-1), kartotinis);
		paskutinis = paskutine;
		switch (Simbolis(0)) {
case -1:
case ')':
case '*':
case '|':
	termas_baigesi = true;
	break;
		}
	} while (!termas_baigesi);

	return saknis;
}

Vertex *CRe::NagrinetiKartotini(Vertex *&paskutine)
{
	Vertex *atomas = NagrinetiAtoma(paskutine);
	Vertex *saknis = NULL, *pabaiga = NULL;

	switch (Simbolis(0)) {
case '*':
	NuskaitykZenkla('*');
	saknis = Vertex::NewVertex();
	pabaiga = Vertex::NewVertex();
	saknis->AddNeighb(new Edge(-1), atomas);
	paskutine->AddNeighb(new Edge(-1), atomas);
	paskutine->AddNeighb(new Edge(-1), pabaiga);
	// jeigu tai butu '+', o ne '*', tai zemiau esancios eilutes nereiketu !!!
	saknis->AddNeighb(new Edge(-1), pabaiga);
	atomas = saknis;
	paskutine = pabaiga;
	break;
	}

	return atomas;
}

Vertex *CRe::NagrinetiAtoma(Vertex *&paskutine)
{
	Vertex *atomas = NULL;

	switch (Simbolis(0)) {
case '.':
	NuskaitykZenkla('.');
	atomas = Vertex::NewVertex();
	paskutine = Vertex::NewVertex();
	atomas->AddNeighb(new Edge(-2), paskutine);
	break;
case '(':
	NuskaitykZenkla('(');
	atomas = NagrinetiIsraiska(paskutine);
	NuskaitykZenkla(')');
	break;
case -1:
case ')':
case '*':
case '|':
	ok = false;
	break;
default:
	atomas = NagrinetiZenkla(paskutine);
	}

	return atomas;
}

Vertex *CRe::NagrinetiZenkla(Vertex *&paskutine)
{
	Vertex *saknis = Vertex::NewVertex();
	char c;

	switch (Simbolis(0)) {
case '/':
	NuskaitykZenkla('/');
	c = NuskaitykZenkla();
	break;
default:
	c = NuskaitykZenkla();
	}
	paskutine = Vertex::NewVertex();
	saknis->AddNeighb(new Edge(c), paskutine);

	return saknis;
}

// ======================= re.cpp ========== end ========================

class MultiVertex;

class MultiEdge {
public:
	MultiEdge(int symbol) {
		this->symbol = symbol;
		this->next = NULL;
		this->into = NULL;
	}
	~MultiEdge() {
	}

	// specialus atvejai: -2 - bet koks simbolis
	int symbol;

	MultiEdge *next;
	MultiVertex *into;
};

class MultiVertex{
public:
	// jeigu naudojame kaip saraso elementa, tai rodo i kita elementa sarase
	MultiVertex *next;

	// virsunes kaimynai
	MultiEdge *links;
	MultiVertex *per_betka;

	// naudojama grafo apejime
	int zyme;

	// aibe, zyminti kurios virsunes is NDFA grafo sudetos i sita virsune
	bool *aibe;

	// zymi, ar tai yra reguliariosios israiskos pabaiga
	// t.y., atejus iki cia galima sakyti, kad suradome
	// reguliariaja israiska atitinkancia simboliu seka
	bool regisr_pabaiga;

	MultiVertex(int visu_kiekis, Vertex **visos, bool *aibe) {
		this->next = NULL;
		this->links = NULL;
		this->per_betka = NULL;
		this->zyme = 0;
		this->regisr_pabaiga = false;
		this->aibe = new bool[visu_kiekis];
		for (int i = 0; i < visu_kiekis; ++i) {
			this->aibe[i] = aibe[i];
			if (aibe[i])
				this->regisr_pabaiga = this->regisr_pabaiga || visos[i]->regisr_pabaiga;
		}
	}

	~MultiVertex() {
		delete[] aibe;
	}

	void AddNeighb(MultiEdge *e, MultiVertex *v) {
		e->next = links;
		e->into = v;
		links = e;
	}

};

int Vertex::count = 0;

void Spausdink(Vertex *saknis, Edge *e = NULL, int tabs = 0) {
	Vertex *temp = saknis;

	while (temp != NULL) {
		for (int i = 0; i < tabs; ++i)
			cout << " ";
		cout << "|";
		if (e != NULL)
			if (e->symbol < 33)
				cout << (int) e->symbol << "  ";
			else
				cout << (char) e->symbol << "  ";
		cout << temp->Id() << " " << temp->regisr_pabaiga << endl;
		if (temp->zyme == 0) {
			temp->zyme = 1;
			Edge *temp2 = temp->links;
			while (temp2 != NULL) {
				Spausdink(temp2->into, temp2, tabs + 1);
				temp2 = temp2->next;
			}
		}
		temp = temp->next;
	}
}

void Spausdink(MultiVertex *saknis, MultiEdge *e = NULL, int tabs = 0) {
	MultiVertex *temp = saknis;

	while (temp != NULL) {
		for (int i = 0; i < tabs; ++i)
			cout << " ";
		if (e != NULL)
			if (e->symbol < 33)
				cout << (int) e->symbol << "  ";
			else
				cout << (char) e->symbol << "  ";
		else
			cout << -1 << "  ";
		for (int i = 0; i < Vertex::count; i++)
			if (temp->aibe[i])
				cout << i << " ";
		cout << "(" << temp->regisr_pabaiga << ")" << endl;
		if (temp->zyme == 0) {
			temp->zyme = 1;
			if (temp->per_betka != NULL)
				Spausdink(temp->per_betka, NULL, tabs + 2);
			MultiEdge *temp2 = temp->links;
			while (temp2 != NULL) {
				Spausdink(temp2->into, temp2, tabs + 2);
				temp2 = temp2->next;
			}
		}
		temp = temp->next;
	}
}

void VirsuniuSurasymas(Vertex *saknis, bool *aplankytos, Vertex **visos)
{
	if ((saknis == NULL) || (aplankytos[saknis->Id()]))
		return;
	visos[saknis->Id()] = saknis;
	aplankytos[saknis->Id()] = true;
	Edge *links = saknis->links;
	while (links != NULL) {
		VirsuniuSurasymas(links->into, aplankytos, visos);
		links = links->next;
	}
}

void VirsunesPerEpsilon(Vertex *saknis, bool *aplankytos)
{
	if (aplankytos[saknis->Id()])
		return;
	aplankytos[saknis->Id()] = true;
	Edge *links = saknis->links;
	while (links != NULL) {
		if (links->symbol == -1)
			VirsunesPerEpsilon(links->into, aplankytos);
		links = links->next;
	}
}

void EpsilonUzdarinys(int kiekis, bool *pradzios, Vertex **visos) {
	bool *aplankytos = new bool[kiekis];
	for (int i = 0; i < kiekis; ++i)
		aplankytos[i] = false;

	for (int i = 0; i < kiekis; ++i)
		if (pradzios[i])
			VirsunesPerEpsilon(visos[i], aplankytos);
	for (int i = 0; i < kiekis; ++i)
		pradzios[i] = aplankytos[i];

	delete[] aplankytos;
}

void VirsunesPer(Vertex *saknis, bool *aplankytos, int ka)
{
	Edge *links = saknis->links;
	while (links != NULL) {
		if (links->symbol == ka)
			aplankytos[links->into->Id()] = true;
		links = links->next;
	}
}

int PatenkaPer(int kiekis, bool *pradzios, Vertex **visos, int ka, bool *patenka) {
	for (int i = 0; i < kiekis; ++i)
		patenka[i] = false;

	for (int i = 0; i < kiekis; ++i)
		if (pradzios[i])
			VirsunesPer(visos[i], patenka, ka);
	int kiek = 0;
	for (int i = 0; i < kiekis; ++i)
		if (patenka[i])
			++kiek;

	return kiek;
}

int mv_kiekis = 0;
int mv_ilgis = 0;
MultiVertex** visos_mv = NULL;

void IsimintiMV(MultiVertex *mv) {
	if (visos_mv == NULL) {
		visos_mv = new MultiVertex*[100];
		mv_ilgis = 100;
	} else if (mv_kiekis == mv_ilgis) {
		MultiVertex **temp = new MultiVertex*[mv_ilgis + 100];
		for (int i = 0; i < mv_kiekis; ++i)
			temp[i] = visos_mv[i];
		delete[] visos_mv;
		mv_ilgis += 100;
		visos_mv = temp;
	}
	visos_mv[mv_kiekis] = mv;
	++mv_kiekis;
}

MultiVertex *TurimeMV(int visu_kiekis, Vertex **visos, bool *aibe) {
	for (int i = 0; i < mv_kiekis; ++i) {
		bool lygios = true;
		for (int ii = 0; ii < visu_kiekis; ++ii)
			if (aibe[ii] != visos_mv[i]->aibe[ii]) {
				lygios = false;
				break;
			}
		if (lygios)
			return visos_mv[i];
	}

	MultiVertex *mv = new MultiVertex(visu_kiekis, visos, aibe);
	IsimintiMV(mv);

	return mv;
}

void MultiGrafoSudarymas(MultiVertex *mv, int visu_kiekis, Vertex **visos) {
	if (mv->zyme == 1)
		return;

	mv->zyme = 1;
	bool *patenka_per_betka = new bool[visu_kiekis];

	// pirmiausiai susirandama virsunes i kurias galima patekti per bet koki
	// simboli (i jas galesime patekti ir per konkrecius simbolius)
	int per_betka_kiekis = PatenkaPer(visu_kiekis, mv->aibe, visos, -2, patenka_per_betka);
	if (per_betka_kiekis > 0) {
		EpsilonUzdarinys(visu_kiekis, patenka_per_betka, visos);
		mv->per_betka = TurimeMV(visu_kiekis, visos, patenka_per_betka);
	}
	delete[] patenka_per_betka;

	bool *patenka = new bool[visu_kiekis];
	for (int i = 0; i < 256; i++) {
		int kiekis = PatenkaPer(visu_kiekis, mv->aibe, visos, i, patenka);
		if (kiekis > 0) {
			if (per_betka_kiekis > 0)
				for (int ii = 0; ii < visu_kiekis; ++ii)
					patenka[ii] = patenka[ii] || mv->per_betka->aibe[ii];
			EpsilonUzdarinys(visu_kiekis, patenka, visos);
			// cia dar reikia patikrinti, ar tokios multi virsunes dar neturime
			// jei neturime - sukuriame nauja, priesingu atveju - pridedame nuoroda
			mv->AddNeighb(new MultiEdge(i), TurimeMV(visu_kiekis, visos, patenka));
		}
	}
	delete[] patenka;

	if (mv->per_betka != NULL)
		MultiGrafoSudarymas(mv->per_betka, visu_kiekis, visos);
	MultiEdge *temp = mv->links;
	while (temp != NULL) {
		MultiGrafoSudarymas(temp->into, visu_kiekis, visos);
		temp = temp->next;
	}
}

void IsvalytiZymes(MultiVertex *mv) {
	if (mv->zyme == 0)
		return;
	mv->zyme = 0;
	if (mv->per_betka != NULL)
		IsvalytiZymes(mv->per_betka);
	MultiEdge *temp = mv->links;
	while (temp != NULL) {
		IsvalytiZymes(temp->into);
		temp = temp->next;
	}
}

int main()
{
	int regexpIlgis = 0;
	int eiluteIlgis = 0;
	char *regexp = NULL;
	char *eilute = NULL;

	pradiniai_duomenys(regexpIlgis, regexp, eiluteIlgis, eilute);
	//cout << (int) strlen(regexp) << "\t\"" << regexp << "\"\n";
	//cout << (int) strlen(eilute) << "\t\"" << eilute << "\"\n";

	//pirmas_sutapimas(regexpIlgis, regexp, eiluteIlgis, eilute, 
	//				 0, 0, 0, rez_pradzia, rez_ilgis);

	//CRe *re = new CRe(29, "(abc|bc)(d|dd)gh(bb|bbb|bbbb)");
	//CRe *re = new CRe(9, "sk*(ab)*s");
	//CRe *re = new CRe(4, "l|is");
	//CRe *re = new CRe(21, "(a|(b|c)|dre(d.e)*)|z");
	//CRe *re = new CRe(9, "ab|(a|c)*");
	//CRe *re = new CRe(8, "ab(.|d)*");
	//CRe *re = new CRe(14, "((a|b)(a|b)*)*");
	//CRe *re = new CRe(24, "((L|l)(a|aa|aaa)bas. *)*");
	//CRe *re = new CRe(19, "((L|l)(a|aa)bas/.)*");
	CRe *re = new CRe(regexpIlgis, regexp);

#ifdef DEBUG
	for (int i = 0; i < re->ilgis; ++i)
		cout << re->regisr[i];
#endif
	cout << endl << "NDFA: " << Vertex::count << " states\t" << re->ok << endl;

	int rez_ok = -1, rez_poz = -1;

	if (re->ok) {
#ifdef DEBUG
		Spausdink(re->Saknis());
#endif

		// bitu masyvas :)
		bool *aplankytos = new bool[Vertex::count];
		for (int i = 0; i < Vertex::count; ++i)
			aplankytos[i] = false;
		// susidedame visas virsunes i paprasta masyva
		Vertex **visos = new Vertex*[Vertex::count];
		for (int i = 0; i < Vertex::count; ++i)
			visos[i] = NULL;
		VirsuniuSurasymas(re->Saknis(), aplankytos, visos);

		for (int i = 0; i < Vertex::count; ++i)
			aplankytos[i] = false;
		aplankytos[0] = true;
		EpsilonUzdarinys(Vertex::count, aplankytos, visos);
		MultiVertex *mv = new MultiVertex(Vertex::count, visos, aplankytos);
		IsimintiMV(mv);
		MultiGrafoSudarymas(mv, Vertex::count, visos);
		IsvalytiZymes(mv);
		
		cout << "DFA: " << mv_kiekis << " states" << endl;
#ifdef DEBUG
		Spausdink(mv);
#endif

		delete[] aplankytos;
		delete[] visos;

		// cia jau prasideda matching'as
		MultiVertex *esame = visos_mv[0];
		int i = -1;
		for (i = 0; i < eiluteIlgis; ++i) {
			char c = eilute[i];
			bool radome_linka = false;
			MultiEdge *temp = esame->links;

			while (temp != NULL) {
				if (temp->symbol == c) {
					radome_linka = true;
					break;
				}
				temp = temp->next;
			}
			if (radome_linka)
				esame = temp->into;
			else if (esame->per_betka != NULL)
				esame = esame->per_betka;
			else
				break;
		}
		
		if (esame->regisr_pabaiga && (i == eiluteIlgis))
			rez_ok = 1;
		else {
			rez_ok = 0;
			if (i < eiluteIlgis)
				rez_poz = i + 1;
			else
				rez_poz = 0;
		}
	}
	if (regexp != NULL)
		delete[] regexp;
	if (eilute != NULL)
		delete[] eilute;

	rezultatai(rez_ok, rez_poz);

	return 0;
}