Answer to Question #176882 in C++ for saif urrehman

Question

Write a C++ program in which, read a c-string from user. Now your task is to find either the entered string is a palindrome or sub-palindrome

Answer 1

#include <bits/stdc++.h>
using namespace std;


int dp[1001][1001];
bool isPal(string s, int i, int j)
{
    if (i > j)
        return 1;


    if (dp[i][j] != -1)
        return dp[i][j];


    if (s[i] != s[j])
        return dp[i][j] = 0;


    return dp[i][j] = isPal(s, i + 1, j - 1);
}


int countSubstrings(string s)
{
    memset(dp, -1, sizeof(dp));
    int n = s.length();
    int count = 0;


    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (isPal(s, i, j))
                count++;
        }
    }
    return count;
}


int main()
{


    char s[50];


    cout <<"Enter a string ";
    cin>>s;
    if(countSubstrings(s)==1)
    {
        cout<<"\nPalindrome";
    }
    else
    {
      if(countSubstrings(s)>1)
      {
        cout<<"\nSub-Palindrome";
      }
      if(countSubstrings(s)==0)
      {
          cout<<"\nNot a palindrome";
      }
    }
    return 0;
}