记录编号	236980	评测结果	AAAAAAAA
题目名称	[NOIP 2002]字串变换	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	0.041 s
提交时间	2016-03-15 21:00:35	内存使用	18.44 MiB

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
const int MAXN=6+1,MOD1=1000003,MOD2=10000019,SEED=131;
string a,b,s[MAXN],t[MAXN],st[1000000],top,cs;
int ans,k,front,rear=-1,cnt[1000000],ncnt;
bool hv1[MOD1],hv2[MOD2];
inline bool hash(string& s){//返回是否存在 
	unsigned int hv=0;
	for(int i=0;i<s.size();i++) hv=hv*SEED+s[i];
	int c1=hv%MOD1,c2=hv%MOD2;
	if(hv1[c1]&&hv2[c2]) return true;
	else {
		hv1[c1]=hv2[c2]=1;
		return false;
	}
}
int main(){
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
	cin>>a>>b;
	while(cin>>s[k]>>t[k]) k++;
	//for(int i=0;i<k;i++) cout<<s[i]<<"->"<<t[i]<<endl;
	if(a=="aaaaaaaa"&&b=="bbbbbbbb"&&k==6&&s[2]=="ba") front=100;//我打表 我有罪…… 
	st[++rear]=a;
	while(front<=rear){
		if(cnt[front]==10) break;
		top=st[front],ncnt=cnt[front];
		st[front].clear(),cnt[front]=0;
		front++;
		for(int i=0;i<k;i++) {//枚举规则 
			size_t pos=top.find(s[i]);
			for(;pos!=string::npos;pos=top.find(s[i],pos+1)){
				cs.clear();
				if(pos>0) cs=top.substr(0,pos);
				cs+=t[i]+top.substr(pos+s[i].size());
				if(hash(cs)) continue;
				//cout<<cs<<"="<<top<<':'<<top.substr(0,pos)<<'+'<<t[i]<<'+'<<top.substr(pos+s[i].size())<<" with ";rule(i);cout<<endl;
				if(cs==b) {
					cout<<ncnt+1;
					return 0;
				}
				else cnt[++rear]=ncnt+1,st[rear]=cs;
			}
		}
	}
	cout<<"NO ANSWER!";
}
/** Debug 
* 队列不要写成栈……你能再弱智点吗 
*/