Fibstring

Tin học trẻ Quảng Ninh 2012 - Bài 3/3
Anna rất thích tính đối xứng, bởi vì một trong các lý do là tên của cô là một xâu đối xứng. Một xâu được gọi là đối xứng nếu việc đọc nó từ trái sang phải và từ phải sang trái là giống nhau.
ở trường Anna được học về dãy xâu Fibonacci f0, f1, … như sau:
   f(0) = a
   f(1) = b
   f(n) = f(n-1) - f(n-2) với mọi n >= 2 (nối của hai xâu Fibonacci liền kề trước).
Như vậy, 5 xâu Fibonacci đầu tiên là: “a”, “b”, “ba”, “bab”, “babba”.
Ngay lập tức Anna quan tâm đến vấn đề trong xâu f(k), xâu con gồm các ký tự liên tiếp đối xứng dài nhất bằng bao nhiêu.
Hãy viết một chương trình giúp Anna giải quyết vấn đề này.
Dữ liệu: Vào từ bàn phím số nguyên k (0 <= k <= 80).
Kết quả: Đưa ra màn hình độ dài xâu con của xâu fk gồm các ký tự liên tiếp, đối xứng dài nhất.
Ví dụ:
       Dữ liệu vào từ bàn phím              Kết quả trên màn hình
                 k = 2                                                 1
                 k = 4                                                 4

                                                           Giải
  Var a,s: array[0..100]of string; + chr$(13) + chr$(10) + _
    d,i,max,k: integer;
Begin
    write('Nhap k: '); readln(k);
    s[0]:='a';
    s[1]:='b';
    i:=2;
    repeat
          s[i]:=s[i-1]+s[i-2];
          i:=i+1;
    until i>k;
    writeln(s[k]);
    max:=1;
    for i:=2 to length(s[k])-1 do
        begin
             d:=0;
             while s[k][i-d]=s[k][i+d+1] do d:=d+1;
             if d*2>max then max:=d*2;
        end;
    write(max);
    readln;
End.