记录编号	38977	评测结果	AAAAAAAAAA
题目名称	基因重组	最终得分	100
用户昵称	isabella	是否通过	通过
代码语言	Pascal	运行时间	2.045 s
提交时间	2012-07-03 12:13:38	内存使用	86.80 MiB

const
 t=5000000;code=390000;
 ten:array[1..12]of longint=(2,11,23,37,43,97,119,973,95,901,123,47);
type
 str=string[12];

 point=^node;
 node=record
  data:str;
  next:point;
  end;
var
 i,j,n,k,l,head,tail,step,tail2:longint;
 s1,s2,s:string;
 c:char;
 p:point;
 ch:array['A'..'Z']of longint;
 b:array[0..390000]of point;
 a:array[1..5000000]of str;

 procedure hash(s:str);
 var i,temp:longint;
 begin
  temp:=0;
  for i:=1 to n do
   temp:=(temp+ten[i]*ch[s[i]])mod code;
  p:=b[temp];
  while p<>nil do
   begin
    if p^.data=s then exit;
    p:=p^.next;
   end;

  new(p);
  p^.data:=s;
  p^.next:=b[temp];
  b[temp]:=p;

  tail:=(tail mod t)+1;a[tail]:=s;
 end;

begin
assign(input,'genea.in');reset(input);
assign(output,'genea.out');rewrite(output);
 ch['A']:=3;ch['C']:=7;ch['T']:=13;ch['G']:=19;
 readln(n);
 readln(s1);readln(s2);

 head:=0;tail:=1;tail2:=1;
 a[1]:=s1;step:=1;
 repeat
  head:=(head mod t)+1;
  s:=a[head];
  s:=s+s[1];
  delete(s,1,1);
  if s=s2 then begin writeln(step);close(input);close(output);halt;end;
  hash(s);

  s:=a[head];
  c:=s[1];s[1]:=s[2];s[2]:=c;
  if s=s2 then begin writeln(step);close(input);close(output);halt;end;
  hash(s);

  if head=tail2 then begin inc(step);tail2:=tail;end;
 until head>=tail;
close(input);close(output);
end.