//Wyszukiwanie palindromow w tekscie
//Rafal Swietlicki
//www.algorytm.org


#include "stdio.h"

#define nmax 30

int dl(char* s)
{
        int i=0;
        while(s[i]) i++;
        return i;
}

int f1(char* s)
{
        int i, j;
        int n=dl(s);
        int wynik=n;
        int m[nmax][nmax];
        for(i=0;i<n-1;i++)
                m[i+1][i]=1;
        for(j=0;j<n;j++)
        {
                m[j][j]=1;
                for(i=j-1;i>=0;i--)
                {
                        m[i][j]=m[i+1][j-1] && s[i]==s[j];
                        wynik+=m[i][j];
                }
        }
        return wynik;
}

int f2(char* s)
{
        int i, j, k;
        int T[nmax+1][nmax+1]={0};
        int n=dl(s);
        for(i=0;i<n;i++)
        {
                T[i][i]=1;
                for(j=i-1;j>=0;j--)
                {
                        T[j][i]=T[j+1][i]+1;
                        for(k=j+1;k<=i;k++)
                                if(s[j]==s[k])
                                        T[j][i]+=T[j+1][k-1]+1;
                }
        }
        return T[0][n-1];
}

int main()
{
        char slowo[nmax];
        printf("Podaj slowo: ");
        scanf("%s",slowo);
        printf("Ilosc spojnych palindromow w slowie %s wynosi %d.\n",slowo,f1(slowo));
        printf("Ilosc niespojnych palindromow w slowie %s wynosi %d.\n",slowo,f2(slowo));
        return 0;
}