Given a String S, count the number of palindrome sub strings in the string. The sub string size starts from 1. i.e., Each individual letters counts as a palindrome.
For Example:
If the given string is "dskjkd", the possible substrings which are palindrome are:
d,s,k,j,k,d,kjk
Hence, the count is 7 (Output)
Implementation:
For Example:
If the given string is "dskjkd", the possible substrings which are palindrome are:
d,s,k,j,k,d,kjk
Hence, the count is 7 (Output)
Implementation:
#include <iostream> #include<cstring> //To use strlen() function #define MAX 100000 //Maximum Range for a char Array using namespace std; int main() { /* Array to get the input string & to store it as char array. For Example: "dskjkd" */ char str[MAX]; /* Waits for user to type input. In our case, str[]="dskjkd" */ cin>>str; /* To get the length of the string */ int len = strlen(str); /* Left pointer (l) & right pointer (r) */ int l,r; /* Initialize left pointer to point to first character of char array */ l = 0; /* Initialize right pointer to point to last character of the char array */ r = len - 1; /* To store count of matching characters at both ends */ int active = 0; /* Loop until the left pointer & right pointer crosses / matches each other */ while( l < r ) { /* a. Check whether first character matches last character b. If it doesn't matches, move "l" to second character, & "r" remains in the same position pointing to last character */ if(str[l] != str[r]) { l++; } /* c. If it matches, move "l" to next successive character & "r" to previous character d. Increment active count */ else { l++; r--; active++; } } /* If there exists at-least a single palindrome with string length as 2, print length of the string + 1, because each character is a palindrome substring + there exists at least one palindrome with length >=2 */ if(active >= 2) { int out = len + 1; cout<<out; } /* If it doesn't exists, print the length of the string , because each character in the string is considered as palindrome with length 1*/ else cout<<len; return 0; }