Xâu fibinacci

[showbiz]

Xét dãy các xâu F1, F2, F3, ..., FN, ... trong đó:
F1 = 'A'
F2 = 'B'
FK+1 = FK + FK-1 (K ³ 2).
Ví dụ:
F1 = 'A'
F2 = 'B'
F3 = 'BA'
F4 = 'BAB'
F5 = 'BABBA'
F6 = 'BABBABAB'
F7 = 'BABBABABBABBA'
F8 = 'BABBABABBABBABABBABAB'
F9 = 'BABBABABBABBABABBABABBABBABABBABBA'
Cho xâu S độ dài không quá 25, chỉ bao gồm các ký tự 'A' và 'B'. Hãy xác định số lần xuất hiện xâu
S trong xâu FN, N £ 35. Chú ý: hai lần xuất hiện của S trong FN không nhất thiết phải là các xâu rời
nhau hoàn toàn.
Dữ liệu: vào từ file van bản FIBISTR.INP, bao gồm nhiều dòng, mỗi dòng có dạng N S. Giữa N và
S có đúng 1 dấu cách. Dữ liệu vào là chuNn, không cần kiểm tra.
Kết quả: Đưa ra file van bản FIBISTR.OUT, mỗi dòng dữ liệu ứng với một dòng kết quả ra

INPUT:

3 A
3 B
8 BABBAB

OUT:

1
0
4

help me! thanks

[Nlseo01]

Xét dãy các xâu F1, F2, F3, ..., FN, ... trong đó:
F1 = 'A'
F2 = 'B'
FK+1 = FK + FK-1 (K ³ 2).
Ví dụ:
F1 = 'A'
F2 = 'B'
F3 = 'BA'
F4 = 'BAB'
F5 = 'BABBA'
F6 = 'BABBABAB'
F7 = 'BABBABABBABBA'
F8 = 'BABBABABBABBABABBABAB'
F9 = 'BABBABABBABBABABBABABBABBABABBABBA'
Cho xâu S độ dài không quá 25, chỉ bao gồm các ký tự 'A' và 'B'. Hãy xác định số lần xuất hiện xâu
S trong xâu FN, N £ 35. Chú ý: hai lần xuất hiện của S trong FN không nhất thiết phải là các xâu rời
nhau hoàn toàn.
Dữ liệu: vào từ file van bản FIBISTR.INP, bao gồm nhiều dòng, mỗi dòng có dạng N S. Giữa N và
S có đúng 1 dấu cách. Dữ liệu vào là chuNn, không cần kiểm tra.
Kết quả: Đưa ra file van bản FIBISTR.OUT, mỗi dòng dữ liệu ứng với một dòng kết quả ra

INPUT:

3 A
3 B
8 BABBAB

OUT:

1
0
4

help me! thanks

dùng mảng để lưu chuỗi tạo ra.
dùng mảng p để lưu kết quả số lần xuất hiện s trong f: p[I] là số lần xuất hiện của s trong xâu f[I].

tính p:
p:=p[i-1] + p[i-2] + số lần xuất hiện của xâu f trong đoạn gồm các kí tự đầu của xâu f[i-1] và các kí tự cuối của xâu f[i-2].

tìm xâu f:
trường hợp length(f[i-1])+ length(f[i-2])<=2*length(s)-2 thì f:=f[i-1]+f[i-2].
trường hợp ngựơc lại thì f:=đoạn đầu f[i-1] + đoạn cuối f[i-2], mỗi đoạn <length(s) kí tự, để đảm bảo xâu của bạn không quá dài và có thể lưu trữ được các xâu phát sinh ngày càng lớn.

bạn xem qua code của mình nè:

function Dau(x: string): string;
begin
       if length(x)<length(s) then exit(x);
       Dau:=copy(x,1,length(s)-1);
end;
function Cuoi(x: string): string;
begin
       if length(x)<length(s) then exit(x);
       Cuoi:=copy(x,length(x)-length(s)+1,length(s)-1);
end;
function chung(x,y: string): longint;
var tam: string;
begin
       tam:=x+y; chung:=0;
       while pos(s,tam)<>0 do
       begin
              if pos(s,tam)>length(x)-length(s)+1 then inc(chung);
              delete(tam,pos(s,tam),1);
       end;
end;
procedure Solve;
var i: longint;
begin
        f[1]:='a'; f[2]:='b';
        for i:=3 to n do
        begin
               p:=p[i-1]+p[i-2]+chung(f[i-1],f[i-2]);
               f:=Dau(f[i-1])+Cuoi(f[i-2]);
       end;
end;