सी++ में पैलिंड्रोम विभाजन

मान लीजिए कि हमारे पास एक इनपुट स्ट्रिंग है, उस स्ट्रिंग का एक विभाजन पैलिंड्रोम विभाजन है, जब विभाजन का प्रत्येक विकल्प एक पैलिंड्रोम होता है। इस खंड में, हमें दिए गए स्ट्रिंग को विभाजित करने वाले पैलिंड्रोम के लिए आवश्यक न्यूनतम कटौती का पता लगाना है। तो अगर स्ट्रिंग "अब्बाबबाबाबाबा" की तरह है, तो पैलिंड्रोम के रूप में विभाजन के लिए न्यूनतम कटौती। यहां 3 कट की जरूरत है। पैलिंड्रोम हैं:a | बब्बब | बी | अबाबा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=str की लंबाई
• कट मैट्रिक्स और पाल मैट्रिक्स को प्रत्येक क्रम n x n परिभाषित करें
• i :=0 से n के लिए, करें
  • pal[i, i] :=true and cut[i, i] :=0
• लेन के लिए 2 से n तक, करें
  • मैं के लिए 0 से n - लेन की सीमा में, करते हैं
    • j :=i + len – 1
    • यदि लेन =2, तो
    • अगर str[i] =str[j], तो pal[i, j] :=true
    • अन्यथा जब str[i] =str[j] और pal[i+1, j-1] ≠ 0 pal[i, j] :=true
    • अगर pal[i, j] सच है, तो कट[i, j] :=0
    • अन्य
      • कट[i, j] :=
      • k के लिए i से j-1 की श्रेणी में, करें
        • कट[i, j] :=न्यूनतम कट[i, j] और (कट[i, k]+ कट[k+1, j+1]+1)
• रिटर्न कट[0, n-1]

उदाहरण

बेहतर समझ प्राप्त करने के लिए आइए निम्नलिखित कार्यान्वयन को देखें -

#include <iostream>
#include <climits>
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 j th 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);
}

इनपुट

ababbbabbababa

आउटपुट

Min cuts for Palindrome Partitioning is: 3