-- Wyszukiwanie palindromow w tekscie
-- (c) 2007 Rafal Swietlicki
-- Implementacja w Ada Tomasz Lubinski
-- www.algorytm.org


with Text_IO;
use Text_IO;

procedure palindromy is

   function f1(s: String) return Integer is
        type BoolArray is array (s'Range) of Boolean;
        m : array (s'Range) of BoolArray;
        wynik: Integer := s'Length;
   begin
        for i in s'First .. s'Last -1 loop
                m(i+1)(i) := TRUE;
        end loop;
                
        for j in s'Range loop
                m(j)(j) := TRUE;
                for i in reverse s'First .. j-1 loop
                        m(i)(j) := m(i+1)(j-1) and s(i)=s(j);
                        if m(i)(j) = TRUE then
                           wynik := wynik + 1;
                        end if;
                end loop;
        end loop;
        return wynik;
   end;

   function f2(s: String) return Integer is
        type IntArray is array (s'First .. s'Last + 1) of Integer;
        T : array (s'First .. s'Last + 1) of IntArray;
   begin
        for i in T'Range loop 
                for j in T(i)'Range loop
                        T(i)(j) := 0;
                end loop;
        end loop;
                        
        for i in s'Range loop
                T(i)(i) := 1;
                for j in reverse s'First .. i-1 loop
                        T(j)(i) := T(j+1)(i)+1;
                        for k in j+1 .. i loop
                                if s(j) = s(k) then
                                        T(j)(i) := T(j)(i) + T(j+1)(k-1)+1;
                                 end if;
                        end loop;
                end loop;
        end loop;
        
        return T(s'First)(s'Last);
   end;


begin

   Put_Line( "Ilosc spojnych palindromow w slowie mama wynosi " & Integer'Image(f1("mama")));
   Put_Line( "Ilosc niespojnych palindromow w slowie mama wynosi " & Integer'Image(f2("mama")));

end;