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;
}