Display all palindromic substring by max length
Given an string which can be containing many palindromic substring. find and display all substring which are contains max length palindrome without overlapping. For example.
Example 1
char str[] = "ABAABACCBAECCCEAAAA";
OutPut :
AECCCEA
ABAABA
CC
B
AAA
Example 2 :
char str[] = "AABAAAAABCCCCBAEFEGH";
ABCCCCBA
AABAA
AA
EFE
G
H
Example 3 :
char str[] = "ABC";
A
B
C
Example 4:
char str[] = "AABECAE";
AA
B
E
C
A
E
Note that each palindromic sequence is displaying in new line. And it can possible same palindromic sequences are exist in more than once but two substring will not overlap. We can solve this problem by using recursion. Here given code implementation process.
//C Program
//Palindromic partitions of a string
#include<stdio.h>
//Function which are check palindrome between substring
int palindrome(char *str,int start,int end)
{
int status=1;
for (start; start < end; start++,end--)
{
if(str[start]!=str[end])
{
status=0;
break;
}
}
return status;
}
void findPalindrome(char *str,int start ,int end)
{
if(start < 0 || start > end) return;
int length=0, x=0, y=0;
//Find largest substring of Palindrome
for (int i = start ; i <= end && i <= end-length ; i++)
{
for (int j = end; j > i ; --j)
{
//When [i] and index [j] values are same
//Then can possible That contains palindrome
if(str[i] == str[j])
{
//Find Palindrome between two index
if(palindrome(str, i, j))
{
//Compare that is longest palindrome ?
if(length < j-i)
{
//Get the length of Palindrome new longest palindrome
length = j-i;
//Get Index Of new longest palindrome
x = i;
y = j;
}
}
}
}
}
if( length > 0)
{
//display substring of a palindrome
for (int i = x ; i <= y ; ++i)
{
printf("%c", str[i] );
}
printf("\n");
//Find Substring Palindrome
findPalindrome(str, start, x-1);
findPalindrome(str, y+1, end);
}
else
{
//When string is not Palindrome
for (int i = start ; i <= end ; ++i)
{
printf("%c\n", str[i] );
}
}
}
int main()
{
char str[] = "ABAABACCBAECCCEAAAA";
//Find the length of string
int size = sizeof(str) / sizeof(str[0]);
findPalindrome(str, 0, size-2);
return 0;
}Output
AECCCEA
ABAABA
CC
B
AAA
//C++ Program
//Palindromic partitions of a string
#include <iostream>
#include <string.h>
using namespace std;
class MyString
{
public:
string str;
//methods
MyString(string);
int palindrome(int,int);
void findPalindrome(int,int);
};
MyString :: MyString( string text)
{
this->str = text;
}
//Function which are check palindrome between substring
int MyString :: palindrome(int start,int end)
{
int status=1;
for (start; start < end; start++,end--)
{
if(str[start]!=str[end])
{
status=0;
break;
}
}
return status;
}
void MyString :: findPalindrome(int start ,int end)
{
if(start < 0 || start > end) return;
int length=0, x=0, y=0;
//Find largest substring of Palindrome
for (int i = start ; i <= end && i <= end-length ; i++)
{
for (int j = end; j > i ; --j)
{
//When [i] and index [j] values are same
//Then can possible That contains palindrome
if(str[i] == str[j])
{
//Find Palindrome between two index
if(palindrome( i, j))
{
//Compare that is longest palindrome ?
if(length < j-i)
{
//Get the length of Palindrome new longest palindrome
length = j-i;
//Get Index Of new longest palindrome
x = i;
y = j;
}
}
}
}
}
if( length > 0)
{
//display substring of a palindrome
for (int i = x ; i <= y ; ++i)
{
cout<<" "<< str[i] ;
}
cout<<endl ;
//Find Substring Palindrome
findPalindrome( start, x-1);
findPalindrome( y+1, end);
}
else
{
//When string is not Palindrome
for (int i = start ; i <= end ; ++i)
{
cout<<" "<< str[i] <<endl ;
}
}
}
int main(){
//Create object
MyString obj = MyString("ABAABACCBAECCCEAAAA");
obj.findPalindrome(0, obj.str.length()-1);
return 0;
}Output
A E C C C E A
A B A A B A
C C
B
A A A
//Java program
//Palindromic partitions of a string
public class MyString
{
private String str;
MyString(String text)
{
this.str = text;
}
public boolean palindrome(int s,int end)
{
boolean status=true;
for (int start=s; start < end; start++,end--)
{
if(str.charAt(start)!=str.charAt(end))
{
status=false;
break;
}
}
return status;
}
public void findPalindrome(int start ,int end)
{
if(start < 0 || start > end) return;
int length=0, x=0, y=0;
//Find largest substring of Palindrome
for (int i = start ; i <= end && i <= end-length ; i++)
{
for (int j = end; j > i ; --j)
{
//When [i] and index [j] values are same
//Then can possible That contains palindrome
if(str.charAt(i) == str.charAt(j))
{
//Find Palindrome between two index
if(palindrome( i, j))
{
//Compare that is longest palindrome ?
if(length < j-i)
{
//Get the length of Palindrome new longest palindrome
length = j-i;
//Get Index Of new longest palindrome
x = i;
y = j;
}
}
}
}
}
if( length > 0)
{
//display substring of a palindrome
for (int i = x ; i <= y ; ++i)
{
System.out.print(" "+str.charAt(i)) ;
}
System.out.println();
//Find Substring Palindrome
findPalindrome( start, x-1);
findPalindrome( y+1, end);
}
else
{
//When string is not Palindrome
for (int i = start ; i <= end ; ++i)
{
System.out.println(" "+str.charAt(i)) ;
}
}
}
public static void main(String[] args)
{
//Create object
MyString obj = new MyString("ABAABACCBAECCCEAAAA");
obj.findPalindrome(0, obj.str.length()-1);
}
}Output
A E C C C E A
A B A A B A
C C
B
A A A
# Python Program
# Display all True Boolean expression
class MyString:
def __init__(self, text):
self.str = text
def palindrome(self, start, end):
status = True
while start < end:
if(self.str[start]!=self.str[end]):
status=False
break
start+=1
end-=1
return status
def findPalindrome(self, start , end):
#base condition
if(start < 0 or start > end):
return
x = 0
y = 0
length = 0
i = start
#Find largest substring of Palindrome
while ( i <= end and i <= end-length):
j = end
while (j>i) :
#When [i] and index [j] values are same
#Then can possible That contains palindrome
if(self.str[i] == self.str[j]):
#Find Palindrome between two index
if(self.palindrome( i, j)):
#Compare that is longest palindrome ?
if(length < j-i):
#Get the length of Palindrome new longest palindrome
length = j-i
#Get Index Of new longest palindrome
x = i
y = j
j-=1
i+=1
if( length > 0):
#display substring of a palindrome
for i in range(x,y+1):
print(" "+self.str[i],end=" ")
print()
#Find Substring Palindrome
self.findPalindrome( start, x-1)
self.findPalindrome( y+1, end)
else:
#When string is not Palindrome
for i in range(start,end+1):
print(" "+self.str[i])
def main():
#Create object
obj = MyString("ABAABACCBAECCCEAAAA")
obj.findPalindrome(0, len(obj.str)-1)
if __name__=="__main__":
main()Output
A E C C C E A
A B A A B A
C C
B
A A A
//C# Program
//Palindromic partitions of a string
using System;
public class MyString
{
public String str;
MyString(String text)
{
this.str = text;
}
public Boolean palindrome(int s,int end)
{
Boolean status=true;
for (int start=s; start < end; start++,end--)
{
if(str[start]!=str[end])
{
status=false;
break;
}
}
return status;
}
public void findPalindrome(int start ,int end)
{
if(start < 0 || start > end) return;
int length=0, x=0, y=0;
//Find largest substring of Palindrome
for (int i = start ; i <= end && i <= end-length ; i++)
{
for (int j = end; j > i ; --j)
{
//When [i] and index [j] values are same
//Then can possible That contains palindrome
if(str[i] == str[j])
{
//Find Palindrome between two index
if(palindrome( i, j))
{
//Compare that is longest palindrome ?
if(length < j-i)
{
//Get the length of Palindrome new longest palindrome
length = j-i;
//Get Index Of new longest palindrome
x = i;
y = j;
}
}
}
}
}
if( length > 0)
{
//display substring of a palindrome
for (int i = x ; i <= y ; ++i)
{
Console.Write(" {0}",str[i]) ;
}
Console.WriteLine();
//Find Substring Palindrome
findPalindrome( start, x-1);
findPalindrome( y+1, end);
}
else
{
//When string is not Palindrome
for (int i = start ; i <= end ; ++i)
{
Console.WriteLine(" {0}",str[i]) ;
}
}
}
public static void Main(String[] args) {
//Create object
MyString obj = new MyString("ABAABACCBAECCCEAAAA");
obj.findPalindrome(0, obj.str.Length-1);
}
}Output
A E C C C E A
A B A A B A
C C
B
A A A
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment