Skip to main content

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.

Display all palindromic substring by max length
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




Comment

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