पलिंड्रोम विभाजन

इस एल्गोरिथम में, इनपुट एक स्ट्रिंग है, उस स्ट्रिंग का एक विभाजन पैलिंड्रोम विभाजन है जब विभाजन का प्रत्येक विकल्प एक पैलिंड्रोम होता है।

इस एल्गोरिथम में, हमें दिए गए स्ट्रिंग को विभाजित करने के लिए पैलिंड्रोम के लिए न्यूनतम कटौती की आवश्यकता है।

इनपुट और आउटपुट

Input:
A string. Say “ababbbabbababa”
Output:
Minimum cut to partition as palindrome. Here 3 cuts are needed.
The palindromes are: a | babbbab | b | ababa

एल्गोरिदम

minPalPart(str)

इनपुट: दी गई स्ट्रिंग।

आउटपुट: स्ट्रिंग से पैलिंड्रोमिक विभाजन की न्यूनतम संख्या।

Begin
   n := length of str
   define cut matrix and pal matrix each of order n x n

   for i := 0 to n, do
      pal[i, i] := true
      cut[i, i] := 0
   done

   for len in range 2 to n, do
      for i in range 0 to n – len, do
         j := i + len – 1
         if len = 2, then
            if str[i] = str[j]
               pal[i, j] := true
         else
            if str[i] = str[j] and pal[i+1, j-1] ≠ 0
               pal[i, j] := true

         if pal[i, j] is true, then
            cut[i, j] := 0
         else

            cut[i, j] := ∞
            for k in range i to j-1, do
               cut[i, j] := minimum of cut[i, j] and (cut[i, k]+ cut[k+1, j+1]+1)
            done
      done
   done
   return cut[0, n-1]
End

उदाहरण

#include <iostream>
using namespace std;

int min (int a, int b) {
   return (a < b)? a : b;
}

int minPalPartion(string str) {
   int n = str.size();

   int cut[n][n];
   bool pal[n][n];              //true when palindrome present for i to jth  element

   for (int i=0; i<n; i++) {
      pal[i][i] = true;         //substring of length 1 is plaindrome
      cut[i][i] = 0;
   }

   for (int len=2; len<=n; len++) {
      for (int i=0; i<n-len+1; i++) {        //find all substrings of length len

         int j = i+len-1;              // Set ending index
         if (len == 2)                 //for two character string
            pal[i][j] = (str[i] == str[j]);
         else                  //for string of more than two characters
            pal[i][j] = (str[i] == str[j]) && pal[i+1][j-1];

         if (pal[i][j] == true)
            cut[i][j] = 0;
         else {
            cut[i][j] = INT_MAX;          //initially set as infinity
            for (int k=i; k<=j-1; k++)
               cut[i][j] = min(cut[i][j], cut[i][k] + cut[k+1][j]+1);
         }
      }
   }
   return cut[0][n-1];
}

int main() {
   string str= "ababbbabbababa";
   cout << "Min cuts for Palindrome Partitioning is:" << minPalPartion(str);
}

आउटपुट

Min cuts for Palindrome Partitioning is: 3