记录编号	39022	评测结果	AAAAAAAAAA
题目名称	基因重组	最终得分	100
用户昵称	IMSL77	是否通过	通过
代码语言	Pascal	运行时间	0.665 s
提交时间	2012-07-03 15:01:07	内存使用	18.28 MiB

program main;
type
  integer=longint;
const
  len=13;
  maxnode=500000;
  p=10000007;
var
  n:integer;
  st,go:string[len];
  Q:array[1..maxnode] of string[len];
  d:array[1..maxnode] of integer;
  hash:array[0..p] of boolean;
  w:array['A'..'Z'] of integer;

  procedure Fopen;
  begin
    assign(input,'genea.in'); reset(input);
    assign(output,'genea.out'); rewrite(output);
  end;

  procedure Fclose;
  begin
    close(input); close(output);
  end;

  procedure Init;
  begin
    readln(n);
    readln(st); readln(go);
    w['A']:=0; w['G']:=1; w['C']:=2; w['T']:=3;
  end;

  function nrep(s:string):boolean;
  var
    i:integer;
    code:integer;
  begin
    code:=0;
    for i:=1 to n do code:=(code shl 2+w[s[i]]) mod p;
    if hash[code] then exit(false);
    hash[code]:=true;
    exit(true);
  end;
  procedure BFS;
  var
    head,tail:integer;
    s,t:string[len];
  begin
    if st=go then begin writeln(0); exit; end;
    fillchar(hash,sizeof(hash),false);
    nrep(st);
    head:=1; tail:=2;
    Q[1]:=st; d[1]:=0;
    repeat
      s:=Q[head];
      t:=s[2]+s[1]+copy(s,3,n-2);
      if nrep(t) then
      begin
        Q[tail]:=t; d[tail]:=d[head]+1;
        if t=go then begin writeln(d[tail]); exit; end;
        inc(tail);
      end;
      t:=copy(s,2,n-1)+s[1];
      if nrep(t) then
      begin
        Q[tail]:=t; d[tail]:=d[head]+1;
        if t=go then begin writeln(d[tail]); exit; end;
        inc(tail);
      end;
      inc(head);
    until head=tail;
  end;
begin
  Fopen;
  Init;
  BFS;
  Fclose;
end.