LQDFIBO - Xâu Fibonacci

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      fo='';
      maxn=1111;
      base=100000000;
      digit=8;
type bignum=array[0..1000] of longint;
     ansistring=string;
var n,cur,k:longint;
    s1,s2,t,st:ansistring;
    l,r,s:array[0..2] of ansistring;
    re:array[0..2] of bignum;
    check:boolean;

procedure rf;
var i:longint;
begin
     assign(input,fi);
     reset(input);
     readln(n); readln(s1); readln(s2); read(t);
     close(input);
end;

function d(s:ansistring):longint;
begin
     d:=length(s);
end;

procedure init;
begin
     k:=d(t)-1; check:=true;
     if d(s1)>=k then
     begin
          l[0]:=copy(s1,1,k);
          r[0]:=copy(s1,d(s1)-k+1,k);
     end
     else
     begin
          l[0]:=s1; r[0]:=s1;
          check:=false;
     end;
     if d(s2)>=k then
     begin
          l[1]:=copy(s2,1,k);
          r[1]:=copy(s2,d(s2)-k+1,k);
     end
     else
     begin
          l[1]:=s2; r[1]:=s2;
          check:=false;
     end;
end;

procedure plus(var c:bignum;a,b:bignum);
var max,i,mem:longint;
begin
     if a[0]>=b[0] then max:=a[0] else max:=b[0];
     mem:=0;
     for i:=1 to max do
     begin
          c[i]:=(a[i]+b[i]+mem) mod base;
          mem:=(a[i]+b[i]+mem) div base;
     end;
     if mem>0 then
     begin
          inc(max);
          c[max]:=mem;
     end;
     c[0]:=max;
end;

function find(t,s:ansistring):longint;
var r,tmp:longint;
begin
     r:=0;
     tmp:=pos(t,s);
     while tmp>0 do
     begin
          inc(r);
          delete(s,1,tmp);
          tmp:=pos(t,s);
     end;
     find:=r;
end;

procedure pr;
var i,pre,last:longint; tmp:bignum;
begin
     init;
     cur:=2;
     re[0,0]:=1; re[0,1]:=find(t,s1);
     re[1,0]:=1; re[1,1]:=find(t,s2);
     s[0]:=s1; s[1]:=s2;
     for i:=3 to n do
     begin
          last:=(cur+2) mod 3;
          pre:=(cur+1) mod 3;
          plus(re[cur],re[last],re[pre]);
          st:='';
          fillchar(tmp,sizeof(tmp),0);
          if check then
          begin
               st:=r[last]+l[pre];
               l[cur]:=l[last];
               r[cur]:=r[pre];
          end
          else
          begin
               st:=s[last]+s[pre];
               if d(st)>=k then
               begin
                    check:=true;
                    l[cur]:=copy(st,1,k);
                    r[cur]:=copy(st,d(st)-k+1,k);
               end
               else
               begin
                    s[cur]:=st;
                    l[cur]:=st; r[cur]:=st;
               end;
          end;
          tmp[0]:=1;
          tmp[1]:=find(t,st);
          plus(re[cur],re[cur],tmp);
          cur:=(cur+1) mod 3;
     end;
end;

procedure wf;
var i,j,t,k:longint; s:string;
begin
     assign(output,fo);
     rewrite(output);
     t:=(n-1) mod 3;
     for i:=re[t,0] downto 1 do
     begin
          if i<re[t,0] then
          begin
               str(re[t,i],s);
               k:=length(s);
               for j:=k+1 to digit do write(0);
          end;
          write(re[t,i]);
     end;
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Download