**QUESTION**

Given a string S, count the number of non empty sub strings that are palindromes. A sub string is any continuous sequence of characters in the string. \n\nA string is said to be palindrome, if the reverse of the string is same as itself.\n\nTwo sub strings are different if they occur at different positions in S\n\nInput\nInput contains only a single line that contains string S.\n\nOutput\nPrint a single number, the number of sub strings that are palindromes.\n\nConstraints\n1 <= |S| <= 50\nS contains only lower case latin letters, that is characters a to z.

**ANSWER**

```
#include<bits/stdc++.h>
using namespace std;
int CountPS(char str[], int n)
{
int dp[n][n];
memset(dp, 0, sizeof(dp));
bool P[n][n];
memset(P, false , sizeof(P));
for (int i= 0; i< n; i++)
P[i][i] = true;
for (int i=0; i<n-1; i++)
{
if (str[i] == str[i+1])
{
P[i][i+1] = true;
dp[i][i+1] = 1 ;
}
}
for (int gap=2 ; gap<n; gap++)
{
for (int i=0; i<n-gap; i++)
{
int j = gap + i;
if (str[i] == str[j] && P[i+1][j-1] )
P[i][j] = true;
if (P[i][j] == true)
dp[i][j] = dp[i][j-1] + dp[i+1][j] + 1 - dp[i+1][j-1];
else
dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1];
}
}
return dp[0][n-1];
}
int main()
{
//char str[] = "abaab";
char str[20];
cin>>str;
//cout<<str;
int n = strlen(str);
cout << CountPS(str, n)+n << endl;
return 0;
}
```