记录编号	9247	评测结果	AAAAAAAA
题目名称	[NOIP 2002]字串变换	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	Pascal	运行时间	0.040 s
提交时间	2009-03-10 21:37:57	内存使用	24.82 MiB

program cch(input,output);
type
 ch=record
     zf:string;
     num:integer;
    end;
 code=record
       data:string;
       rchild:integer;
       lchild:integer;
      end;
var
 c:array[1..100000] of ch;
 s1,s2,s3,s:string;
 a,b:array[1..10] of string;
 i,head,tail,tot,j,now,q:longint;
 d:array[0..1000] of integer;
 {f:array[1..100000] of code;}
 hash:array[0..100000] of boolean;

function check(s:string):boolean;
var
 h,i,g:longint;
begin
 h:=0;
 for i:=1 to length(s) do
  begin
   h:=(h shl 4)+ord(s[i]);
   g:=h and $f0000000;
   h:=(h xor (g shr 24))and ( not g);
  end;
 h:=h mod 50000;
 if hash[h] then
  begin
   hash[h]:=false; exit(true);
  end;
 exit(false);
end;


{function check(s:string):boolean;
var
 t,ft:longint;
 flag:boolean;
begin
 t:=1; ft:=0; flag:=true;
 while t<>0 do
  if s=f[t].data then exit(false)
   else
    if s>f[t].data then
     begin
      ft:=t; t:=f[ft].rchild;
      flag:=true;
     end
    else
     begin
      ft:=t; t:=f[ft].lchild;
      flag:=false;
     end;
 inc(q); f[q].data:=s; f[q].lchild:=0; f[q].rchild:=0;
 if flag then f[ft].rchild:=q
         else f[ft].lchild:=q;
 exit(true);
end;}

begin
 assign(input,'string.in');
 assign(output,'string.out');
 reset(input);
 rewrite(output);
 readln(s);
 fillchar(hash,sizeof (hash),true);
 s1:=copy(s,1,pos(' ',s)-1);
 delete(s,1,pos(' ',s));
 s2:=s;
 tot:=0;
 while not eof(input) do
  begin
   readln(s);
   inc(tot);
   a[tot]:=copy(s,1,pos(' ',s)-1);
   delete(s,1,pos(' ',s));
   b[tot]:=s;
  end;
 q:=1; {f[q].data:=s1; f[q].rchild:=0; f[q].lchild:=0;}
 head:=1; tail:=1;
 c[head].zf:=s1; c[head].num:=0;
 repeat
  for i:=1 to tot do
    begin
      s3:=c[head].zf; d[0]:=0; now:=0;
      while pos(a[i],s3)<>0 do
       begin
        inc(d[0]);
        d[d[0]]:=pos(a[i],s3)+now;
        delete(s3,pos(a[i],s3),length(a[i]));
        now:=now+length(a[i]);
       end;
      for j:=1 to d[0] do
       begin
        s3:=c[head].zf;
        delete(s3,d[j],length(a[i]));
        insert(b[i],s3,d[j]);
        if check(s3)and(length(s3)<=115) then
         begin
          inc(tail);
          c[tail].zf:=s3; c[tail].num:=c[head].num+1;
          if c[tail].num>10 then
           begin
            write('NO ANSWER!');
            close(input); close(output);
            halt;
           end;
         end;
        if s3=s2 then
         begin
          write(c[tail].num);
          close(input); close(output);
          halt;
         end;
       end;
    end;
   inc(head);
  until head>tail;
 write('NO ANSWER!');
 close(input); close(output);
end.