#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<fstream>
#include<string>
#include<cstring>
#include<queue>

using namespace std;

// -----------------------------------Gramatica------------------------

struct G
{
	string P1[100];
	char S,P0[100];
	int size;
};

void Limbaj(G a,int k,string c="")
{
	if(c=="")c=a.S;
	if(k>=c.size())
	{
		if(c[c.size()-1]<='z'&&c[c.size()-1]>='a')
			cout<<c<<"\n";
		for(int i=0;i<a.size;i++)
		{
			if(a.P0[i]==c[c.size()-1])
			{
				string aux=c;
				aux.erase(aux.end()-1);
				aux+=a.P1[i];
				Limbaj(a,k,aux);
			}
		}
	}
}

G citG(istream& in)
{
	G a;
	in>>a.S;
	in>>a.size;
	for(int i=0;i<a.size;i++)
		in>>a.P0[i]>>a.P1[i];
	return a;
}

//----------------------------liste--------------------------------

struct nod
{
	int i;
	nod *n;
};

void push_back(nod*&n,int x)
{
	if(!n)
	{
		n=new nod;
		n->n=NULL;
		n->i=x;
	}
	else push_back(n->n,x);
}


//-----------------------------AFD---------------------------------

struct AFD
{
	int q_act,q0,tranz[100][26],nr_stari;
	bool finale[100];
	AFD(int x=100)
	{
		nr_stari=x;
		for(int i=0;i<nr_stari;i++)
		{
			finale[i]=false;
			for(int j=0;j<26;j++)
				tranz[i][j]=-1;
		}
	}
};

void Limbaj(AFD a,int k,string c="")
{
	if(c=="")a.q_act=a.q0;
	if(k>=c.size())
	{
		if(a.finale[a.q_act])
			cout<<c<<"\n";
		for(int i=0;i<26;i++)
			if(a.tranz[a.q_act][i]!=-1)
			{
				string aux=c+(char)(i+'a');
				int iaux=a.q_act;
				a.q_act=a.tranz[a.q_act][i];
				Limbaj(a,k,aux);
				a.q_act=iaux;
			}
	}
}

bool valid(AFD a,string str)
{
	a.q_act=a.q0;
	for(int i=0;i<str.size();i++)
	{
		if(a.tranz[a.q_act][str[i]-'a']==-1)return false;
		a.q_act=a.tranz[a.q_act][str[i]-'a'];
	}
	if(a.finale[a.q_act])return true;
	return false;
}


AFD citAFD(istream& in)
{
	AFD a;
	int t;
	in>>a.q0>>t>>a.nr_stari;
	for(int i=0;i<a.nr_stari;i++)
	{
		int x;
		in>>x;
		if(x)
			a.finale[i]=true;
	}
	for(int i=0;i<t;i++)
	{
		int a1,a2;
		char a3;
		in>>a1>>a3>>a2;
		a.tranz[a1][a3-'a']=a2;
	}
	return a;
}
//--------------------------------------AFN--------------------------------------

struct AFN
{
	int q_act,q0,nr_stari;
	nod*tranz[100][26];
	bool finale[100];
	AFN(int x=100)
	{
		nr_stari=x;
		for(int i=0;i<nr_stari;i++)
		{
			finale[i]=false;
			for(int j=0;j<26;j++)
				tranz[i][j]=NULL;
		}
	}
};

void Limbaj(AFN a,int k,string c="")
{
	if(c=="")a.q_act=a.q0;
	if(k>=c.size())
	{
		if(a.finale[a.q_act])
			cout<<c<<"\n";
		for(int i=0;i<26;i++)
		{
			nod *pnaux=a.tranz[a.q_act][i];
			int iaux=a.q_act;
			string saux=c+(char)(i+'a');
			while(pnaux)
			{
				a.q_act=pnaux->i;
				Limbaj(a,k,saux);
				pnaux=pnaux->n;
			}
			a.q_act=iaux;
		}
	}
}

bool valid(AFN a,string str)
{
	int p,u,k,c[100];
	p=0;
	c[p]=a.q0;
	u=k=1;
	for(int i=0;i<str.size();i++)
	{
		if(p==u)return false;
		nod*pnaux;
		while(p<k)
		{
			pnaux=a.tranz[c[p%100]][str[i]-'a'];
			while(pnaux)
			{
				c[(u++)%100]=pnaux->i;
				pnaux=pnaux->n;
			}
			p++;
		}
		k=u;
	}
	while(p<u)
	{
		if(a.finale[c[p%100]])
			return true;
		p++;
	}

	return false;
}


AFN citAFN(istream&in)
{
	int t;
	AFN a;
	in>>a.q0>>t>>a.nr_stari;
	for(int i=0;i<a.nr_stari;i++)
	{
		int x;
		in>>x;
		if(x)
			a.finale[i]=true;
	}
	for(int i=0;i<t;i++)
	{
		int a1,a2;
		char a3;
		in>>a1>>a3>>a2;
		push_back(a.tranz[a1][a3-'a'],a2);
	}
	return a;
}
//---------------------------------lambda AFN------------------------------------

struct lAFN:public AFN
{
	nod*ltranz[100];
	lAFN(int x=100):AFN(x)
	{
		for(int i=0;i<nr_stari;i++)
			ltranz[i]=NULL;
	}
};

void Limbaj(lAFN a,int k,string c="")
{
	if(c=="")a.q_act=a.q0;
	if(k>=c.size())
	{
		if(a.finale[a.q_act])
			cout<<c<<"\n";
		nod*pnaux=a.ltranz[a.q_act];
		int iaux=a.q_act;
		while(pnaux)
		{
			a.q_act=pnaux->i;
			pnaux=pnaux->n;
			Limbaj(a,k,c);
		}
		a.q_act=iaux;
		for(int i=0;i<26;i++)
		{
			pnaux=a.tranz[a.q_act][i];
			while(pnaux)
			{
				a.q_act=pnaux->i;
				pnaux=pnaux->n;
				string saux=c+(char)(i+'a');
				Limbaj(a,k,saux);
			}
			a.q_act=iaux;
		}
	}
}

bool valid(lAFN a,string str)
{
	int u=1,p=0,k=u,c[1000];
	c[p]=a.q0;
	nod*pnaux;
	for(int i=0;i<str.size();i++)
	{
		if(p==u)return false;
		for(int j=p;j<u;j++)
		{
			pnaux=a.ltranz[c[j%1000]];
			while(pnaux)
			{
				c[(u++)%1000]=pnaux->i;
				pnaux=pnaux->n;
			}
		}
		k=u;
		for(;p<k;p++)
		{
			pnaux=a.tranz[c[p%1000]][str[i]-'a'];
			while(pnaux)
			{
				c[(u++)%1000]=pnaux->i;
				pnaux=pnaux->n;
			}
		}
	}
	for(int j=p;j<u;j++)
	{
		pnaux=a.ltranz[c[j%1000]];
		while(pnaux)
		{
			c[(u++)%1000]=pnaux->i;
			pnaux=pnaux->n;
		}
	}
	for(;p<u;p++)
		if(a.finale[c[p%100]])
			return true;
	return false;
}

lAFN citlAFN(istream&in)
{
	int t;
	lAFN a;
	in>>a.q0>>t>>a.nr_stari;
	for(int i=0;i<a.nr_stari;i++)
	{
		int x;
		in>>x;
		if(x)
			a.finale[i]=true;
	}
	for(int i=0;i<t;i++)
	{
		int a1,a2;char a3;
		in>>a1>>a3>>a2;
		if(a3=='0')
		{
			push_back(a.ltranz[a1],a2);
			continue;
		}
		push_back(a.tranz[a1][a3-'a'],a2);
	}
	return a;
}
//-------------------------------------TRIE--------------------------------------

struct TRIE
{
	TRIE*fiu[26];
	int nrfii,cnt;
	TRIE()
	{
		cnt=nrfii=0;
		memset(fiu,0,sizeof(fiu));
	}
};

void add(TRIE *&a,string str)
{
	TRIE *aux=a;
	for(int i=0;i<str.size();i++)
	{
		if(!a->fiu[str[i]-'a'])
		{
			a->fiu[str[i]-'a']=new TRIE;
			a->nrfii++;
		}
		a=a->fiu[str[i]-'a'];
	}
	a->cnt++;
	a=aux;
}

void rem(TRIE*&a,string str)
{
	TRIE **stiva=(TRIE**)malloc(sizeof(TRIE*)*str.size());
	for(int i=0;i<str.size();i++)
	{
		stiva[i]=a;
		a=a->fiu[str[i]-'a'];
	}
	a->cnt--;
	for(int i=str.size()-1;i>=0;i--)
	{
		if(stiva[i]->fiu[str[i]-'a']->cnt==0&&stiva[i]->fiu[str[i]-'a']->nrfii==0)
		{
			delete stiva[i]->fiu[str[i]-'a'];
			stiva[i]->nrfii--;
			stiva[i]->fiu[str[i]-'a']=0;
		}
	}
	a=stiva[0];
	if(!a->fiu[str[0]-'a'])a->nrfii--;
}

int aparitii(TRIE *a,string str)
{
	for(int i=0;i<str.size();i++)
	{
		if(a->fiu[str[i]-'a'])
			a=a->fiu[str[i]-'a'];
		else
			return 0;
	}
	return a->cnt;
}

int prefix(TRIE *a,string str)
{
	int k=0;
	for(int i=0;i<str.size();i++)
		if(a->fiu[str[i]-'a'])
		{
			k++;
			a=a->fiu[str[i]-'a'];
		}
		else
			return k;
	return k;
}
		


//-------------------------------------main--------------------------------------
int main()
{
	G a1;
	AFD a2;
	AFN a3;
	lAFN a4;
	TRIE *a5=new TRIE;
	cout<<"Alege optiunea:\n";
	cout<<"1.Limbaj recunoscut de o gramatica,cuvintele <= k;\n";
	cout<<"2.Limbaj recunoscut de un AFD, cuvintele <=k;\n";
	cout<<"3.Limbaj reconuscut de un AFN, cuvintele <=k;\n";
	cout<<"4.Limbaj recunoscut de un Lambda AFN, cuvintele <=k;\n";
	cout<<"5.W apartine lui L(AFD);\n";
	cout<<"6.W apartine lui L(AFN):\n";
	cout<<"7.W apartine lui L(Lambda AFN);\n";
	cout<<"8.Trie;\n";
	int x,k;
	string W;
//	cin>>x;
	x=8;
	ifstream f;
	ofstream g;
	switch (x)
	{
		case 1:
			f.open("Gram.in");
			a1=citG(f);
			cout<<"k=";
			cin>>k;
			Limbaj(a1,k);
			break;
		case 2:
			f.open("AFD.in");
			a2=citAFD(f);
			cout<<"k=";
			cin>>k;
			Limbaj(a2,k);
			break;
		case 3:
			f.open("AFN.in");
			a3=citAFN(f);
			cout<<"k=";
			cin>>k;
			Limbaj(a3,k);
			break;
		case 4:
			f.open("lAFN.in");
			a4=citlAFN(f);
			cout<<"k=";
			cin>>k;
			Limbaj(a4,k);
			break;
		case 5:
			f.open("AFD.in");
			a2=citAFD(f);
			cout<<"W=";
			cin>>W;
			if(W=="0")
				W="";
			if(valid(a2,W))
				cout<<"Apartine limbajului!\n";
			else
				cout<<"Nu apartine limbajului!\n";
			break;
		case 6:
			f.open("AFN.in");
			a3=citAFN(f);
			cout<<"W=";
			cin>>W;
			if(W=="0")
				W="";
			if(valid(a3,W))
				cout<<"Apartine limbajului!\n";
			else
				cout<<"Nu apartine limbajului!\n";
			break;
		case 7:
			f.open("lAFN.in");
			a4=citlAFN(f);
			cout<<"W=";
			cin>>W;
			if(W=="0")
				W="";
			if(valid(a4,W))
				cout<<"Apartine limbajului!\n";
			else
				cout<<"Nu apartine limbajului!\n";
			break;
		case 8:
			f.open("trie.in");
			g.open("trie.out");
			while(!f.eof())
			{
				f>>x;
				if(!f.eof())
				{
					f>>W;
					switch(x)
					{
						case 0:
							add(a5,W);
							break;
						case 1:
							rem(a5,W);
							break;
						case 2:
							g<<aparitii(a5,W)<<"\n";
							break;
						case 3:
							g<<prefix(a5,W)<<"\n";
							break;
					}
				}
			}
			break;
	}
	f.close();
	g.close();
	return 0;
}