In tất cả các phân vùng palindromic của một chuỗi trong C ++

Trong bài toán này, chúng ta có một chuỗi palindromic. Và chúng ta phải in tất cả các phân vùng của chuỗi này. Trong bài toán này, chúng tôi sẽ tìm tất cả các phân vùng palindrome có thể có của chuỗi bằng cách cắt nó.

Hãy lấy một ví dụ để hiểu vấn đề -

Đầu vào - string =‘ababa’
Đầu ra - ababa, a bab a, a b a b a….

Giải pháp cho vấn đề này là kiểm tra xem một chuỗi con có phải là palindrome hay không. Và in chuỗi con nếu nó là chuỗi con.

Ví dụ

Chương trình dưới đây sẽ minh họa giải pháp -

#include<bits/stdc++.h>
using namespace std;
bool isPalindrome(string str, int low, int high){
   while (low < high) {
      if (str[low] != str[high])
         return false;
      low++;
      high--;
   }
   return true;
}
void palindromePartition(vector<vector<string> >&allPart, vector<string> &currPart, int start, int n, string str){
   if (start >= n) {
      allPart.push_back(currPart);
      return;
   }
   for (int i=start; i<n; i++){
      if (isPalindrome(str, start, i)) {
         currPart.push_back(str.substr(start, i-start+1));
         palindromePartition(allPart, currPart, i+1, n, str);
         currPart.pop_back();
      }
   }
}
void generatePalindromePartitions(string str){
   int n = str.length();
   vector<vector<string> > partitions;
   vector<string> currPart;
   palindromePartition(partitions, currPart, 0, n, str);
   for (int i=0; i< partitions.size(); i++ ) {
      for (int j=0; j<partitions[i].size(); j++)
      cout<<partitions[i][j]<<" ";
      cout<<endl;
   }
}
int main() {
   string str = "abaaba";
   cout<<"Palindromic partitions are :\n";
   generatePalindromePartitions(str);
   return 0;
}

Đầu ra

Palindromic partitions are :
a b a a b a
a b a aba
a b aa b a
a baab a
aba a b a
aba aba
abaaba