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

public class Palindromy {

	public static int f1(String s)
	{
	        int i, j;
	        int n = s.length();
	        int wynik=n;
	        boolean m[][] = new boolean[n][n];
	        for(i=0;i<n-1;i++)
	                m[i+1][i]= true;
	        for(j=0;j<n;j++)
	        {
	                m[j][j]=true;
	                for(i=j-1;i>=0;i--)
	                {
	                        m[i][j]=m[i+1][j-1] && s.charAt(i)==s.charAt(j);
	                        if (m[i][j])
	                        {
	                           wynik++;
	                        }
	                }
	        }
	        return wynik;
	}

	public static int f2(String s)
	{
	        int n=s.length();
	        int T[][] = new int [n+1][n+1];
	        for(int i=0;i<n;i++)
	        {
	                T[i][i]=1;
	                for(int j=i-1;j>=0;j--)
	                {
	                        T[j][i]=T[j+1][i]+1;
	                        for(int k=j+1;k<=i;k++)
	                                if(s.charAt(j)==s.charAt(k))
	                                        T[j][i]+=T[j+1][k-1]+1;
	                }
	        }
	        return T[0][n-1];
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
        String slowo;
        System.out.println("Podaj slowo: ");
        slowo = Console.readString();
        System.out.println("Ilosc spojnych palindromow w slowie " + slowo + " wynosi " + f1(slowo));
        System.out.println("Ilosc niespojnych palindromow w slowie " + slowo + " wynosi " + f2(slowo));
	}

}