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.