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

const
  bit:array[1..24] of longint=(1,3,7,15,31,63,127,255,511,1023,
  2047,4095,8191,16383,32767,65535,131071,262143,524287,1048575,
  2097151,4194303,8388607,16777215);
var
  i,j,len,num1,num2,new,head,tail,be,en:longint;
  s1,s2:string;
  p:array[1..17000000] of boolean;
  d:array[1..1000000] of longint;
  step:array[1..1000000] of longint;
  procedure inf;
  begin
    assign(input,'genea.in'); reset(input);
    assign(output,'genea.out'); rewrite(output);
    readln(len);
    readln(s1);
    readln(s2);
    for i:=1 to len do
      begin
        be:=be shl 2;
        case s1[i] of
          'A':be:=be+0;
          'C':be:=be+1;
          'G':be:=be+2;
          'T':be:=be+3;
        end;
      end;
    for i:=1 to len do
      begin
        en:=en shl 2;
        case s2[i] of
          'A':en:=en+0;
          'C':en:=en+1;
          'G':en:=en+2;
          'T':en:=en+3;
        end;
      end;
  end;
  procedure outf;
  begin
    writeln(step[tail]);
    close(input); close(output);
    halt;
  end;
  procedure bfs;
  begin
    head:=0;
    tail:=1;
    d[1]:=be;
    p[be]:=true;
    repeat
      inc(head);
      num1:=d[head] shr (len*2-2);
      num2:=(d[head] shr (len*2-4)) and bit[2];
      new:=(num2 shl 2+num1) shl (len*2-4)+d[head] and bit[len*2-4];
      if p[new]=false then
        begin
          p[new]:=true;
          inc(tail);
          d[tail]:=new;
          step[tail]:=step[head]+1;
          if new=en then outf;
        end;
      num1:=(d[head] shl 2) and bit[len*2];
      num2:=d[head] shr (len*2-2);
      new:=num1+num2;
      if p[new]=false then
        begin
          p[new]:=true;
          inc(tail);
          d[tail]:=new;
          step[tail]:=step[head]+1;
          if new=en then outf;
        end;
    until head>=tail;
  end;
begin
  inf;
  bfs;
  outf;
end.