Print all Palindromic Substrings of the given string – SET 1

“Print all Palindromic Substrings of the given string” is a basic problem of string data structure asked in many technical interviews. Here, we are given a string of length ‘n’ and our task is to write a program to print all palindromic substrings of the given string.

Palindromic Substring are those substrings of given string, which are also palindrome.

Example:

INPUT:
ABAPXP
OUTPUT:
A
ABA
B
A
P
PXP
X
P
P

The steps required to print all palindromic substrings of the given string are as follows:

1. Three loops will be taken.
2. The outer loop will be used for starting character of palindromic substring.
3. The middle loop will be used for ending character of the palindromic substring.
4. The inner most loop will be used for creating the substring from starting character (outer loop) to ending character (middle loop).
5. For every substring created in inner loop, we will check whether it is palindromic string or not. If it is palindromic string, we will print it.

The time complexity of this solution is O(n⁴), where ‘n’ is the length of the string.

C++ Program to print all palindromic substrings of the given string is as follows:

/* C++ Program to print all palindromic substrings of the given string */  
#include<bits/stdc++.h>  
using namespace std;  
/* Function to check whether string is palindrome or not */  
bool palindromic(string str)  
{  
    string temp = str;  
    reverse(temp.begin(),temp.end());  
    if(str == temp)  
    return true;  
    return false;  
}  
int main()  
{  
    string str;  
    cout<<"Enter a string:\n";  
    cin>>str;  
    cout<<"The Palindromic substring are:\n";  
    int size = str.length();  
    /* Outer loop for starting character of substring */  
    for(int i = 0; i < size; i++)  
    {  
        /* Middle loop for ending character of substring */  
        for(int j = i; j < size; j++)  
        {  
            string substring = "";  
            /* Inner loop for creating substring */  
            for(int k = i; k <= j; k++)  
            {  
                substring = substring + str[k];  
            }  
            /* Function to check whether string is palindrome or not */  
            if(palindromic(substring))  
            cout<<substring<<"\n";  
        }  
    }  
}  

OUTPUT:
Enter a string: 
ABAPXP
The Palindromic substring are:
A
ABA
B
A
P
PXP
X
P

Related Posts:

1. Program to check Panagram String.
2. Program to find first non-repeating character of the String.
3. Program to Reverse a String.
4. Program to Count Number of Characters in a String.
5. Program to Count frequency of particular character of the String.
6. Program to Count Number of Vowels and Number of Consonants in a String.
7. Program to Check if String is alphabetic or numeric or alpha-numeric.
8. Program to copy one String to Another.
9. Program to Concatenate Two Strings.
10. Program to Check whether given String is Palindrome or not.
11. Program to convert lower-case alphabet to upper-case alphabet and vice-versa.
12. Program to count total number of words in a string.
13. Program to find smallest and largest word of the String.
14. Program to find Most Frequent Character of the String.
15. Program to Remove all the blank spaces from the String.
16. Program to check if String is isogram or not.
17. Program to Reverse Each word of the String.
18. Program to Print All the Substring of the Given String.
19. Program to find longest palindromic Substring.
20. Program to check Anagram Strings.