uva 310 L-system Lシステムハッシュ判定とTLE

この問題は私が繰り返し実験した結果、ハッシュで重さを判断するのはTLEで、直接mapでマークするのはタイムアウトしないで、ハッシュ関数の設計が悪いと感じて、もし一人一人が計算するのは確かに複雑度が少し高いならば、最高は15位があります.
題意がよくわかりませんが、指定された列(3行目)からaに出会うと1行目を入力する非空子セットに置き換えられ、bに換えると2行目を入力する非空子セットに置き換えられ、4行目の文字列を生成できるかどうかを尋ねるという意味です.
私のやり方は他の人のコードを参考にして、aに出会ったら最初の行に置き換えて、bに出会ったらbに置き換えて、それから新しい文字列の子列が要求に合っているかどうかを判断して、このように考えてみると確かに簡単に理解しなければなりません.もちろんもう一つの考え方は,置換時にサブストリングに置き換えることであり,サブストリングを遍歴する必要があり,本にも対応するアルゴリズムがあり,実現は難しくない.

//12:27
#include<iostream>
#include<cstring>
#include<string>
#include<map>
#include<cstdio>
using namespace std;


//const int MAXSIZE = 1 <<16;
map<string,int> hashmap;
string a,b,w,g,S[230000];
int front,rear;
bool flag;




void is_contain(string ns)
{
	for (int i=0;i<ns.length()-1;i++)
		{
			string substr="";
			for (int j=i;j<i+g.length()&&j<ns.length();j++)
				substr += ns[j];
			if (substr==g)
			{
				flag=1;
				cout<<"YES"<<endl;
				return;
			}
			else if (!hashmap[substr])
			{
				S[rear++]=substr;
				hashmap[substr]=1;
			}
			
		}
}
void bfs ()
{
	hashmap.clear();
	front=1;rear=2;
	flag=0;
	S[1]=w;
	hashmap[w]=1;
	if(w.size()>=g.size())   is_contain(w);
	if (flag)
		return;
	while (front<rear)
	{
		string ns = "";
		for (int k=0;k<S[front].length();k++)
		{
			if (S[front][k]=='a')
				ns += a;
			else ns += b;
		}
		is_contain(ns);
		if (flag) return;
		front++;
	}
}
int main()
{
	
	while (cin>>a>>b>>w>>g)
	{
		bfs();
		if (!flag) cout<<"NO"<<endl;
	}
	return 0;
}