//Wyszukiwanie palindromow w tekscie
//Rafal Swietlicki
//Implementacja Delphi Tomasz Lubinski
//www.algorytm.org

program Palindromy;
{$APPTYPE CONSOLE}
uses
  SysUtils;

function f1(s: String): Integer;
var
   i, j, n: Integer;
   m: array of array of Boolean;
begin
        n := Length(s);
        setLength(m, n);
        for i:=0 to n-1 do
           setLength(m[i], n);

        for i:=0 to n-1 do
            for j:=0 to n-1 do
               m[i][j] := false;

        Result := n;
        for i:=0 to n-2 do
                m[i+1][i] := true;

        for j:=0 to n-1 do
        begin
                m[j][j] := true;
                for i:=j-1 downto 0 do
                begin
                        m[i][j] := (m[i+1][j-1]) and (s[i+1]=s[j+1]);
                        if  m[i][j] = true then
                              Result := Result + 1;
                end;
        end;
end;

function f2(s: String): Integer;
var
        i, j, k, n: Integer;
        T: array of array of Integer;
begin
        n := Length(s);
        setLength(T, n+1);
        for i:=0 to n do
           setLength(T[i], n+1);

        for i:=0 to n do
            for j:=0 to n do
               T[i][j] := 0;

        for i:=0 to n-1 do
        begin
                T[i][i] := 1;
                for j:=i-1 downto 0 do
                begin
                        T[j][i] := T[j+1][i]+1;
                        for k:=j+1 to i do
                                if s[j+1]=s[k+1] then
                                        T[j][i] := T[j][i]+T[j+1][k-1]+1;
                end;
        end;
        Result := T[0][n-1];
end;

var
        slowo: String;
begin
        writeln('Podaj slowo: ');
        readln(slowo);
        writeln('Ilosc spojnych palindromow w slowie ' + slowo + ' wynosi ' + IntToStr(f1(slowo)));
        writeln('Ilosc niespojnych palindromow w slowie ' + slowo + ' wynosi ' + IntToStr(f2(slowo)));

        readln;
end.