Print all Palindromic Substrings of the String – SET 1

Print all Palindromic Substrings of the 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 print all the palindromic substring of the given string.

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

Example:

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

The steps required to print all the palindromic substring of the given strings 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^4), where ‘n’ is the length of the string.

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

```/* Program to print all the palindromic substring of the 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: