记录编号	435940	评测结果	WWAWWWWW
题目名称	[NOIP 2002]字串变换	最终得分	12
用户昵称	Hzoi_Hugh	是否通过	未通过
代码语言	C++	运行时间	0.018 s
提交时间	2017-08-10 19:19:42	内存使用	9.85 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
using namespace std;
namespace Hash{
  int P=10000007,K=133;
  bool hash[10000007]={0};
  inline int Hash(string s){
    int len=s.size(),ret=0;
    for(int i=0;i<len;i++)
      ret=(ret*K%P+s[i])%P;
    return ret;
  }
  inline bool exit(string s){
    return hash[Hash(s)];
  }
}
vector<string> nxt,now;
string a,b,ss[10][2];
int n;
map<string,bool> mm;
int main(){
  freopen("string.in","r",stdin);
  freopen("string.out","w",stdout);
  cin>>a>>b;
  while(cin>>ss[++n][0]>>ss[n][1]){};n--;
  now.push_back(a);
  for(int k=1;k<=10;k++){
    nxt.clear();
    for(int i=0;i<now.size();i++){
      //cout<<now[i]<<endl;
      for(int j=1;j<=n;j++)
        if(now[i].find(ss[j][0],0)!=string::npos){
          int pos=0;
          while(now[i].find(ss[j][0],pos)!=string::npos){
            string s=now[i];
            pos=now[i].find(ss[j][0],pos);
            s=s.replace(pos,ss[j][0].size(),ss[j][1]);
            if(Hash::exit(s)==0){
              Hash::hash[Hash::Hash(s)]=1;
              if(s==b){printf("%d\n",k);return 0;}
              nxt.push_back(s);
            }
            pos+=ss[j][0].size();
          }
        }
    }
    now=nxt;
  }
  printf("NO ANSWER!\n");
  return 0;
}