PALINDROME COUNT

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;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro