Phân vùng Palindrome trong C ++

Giả sử chúng ta có một chuỗi đầu vào, một phân vùng của chuỗi đó là phân vùng palindrome, khi mọi chuỗi con của phân vùng là một palindrome. Trong phần này, chúng ta phải tìm các đường cắt tối thiểu cần thiết để phân vùng palindrome cho chuỗi đã cho. Vì vậy, nếu chuỗi giống như "ababbbabbababa" Cắt tối thiểu để phân vùng là palindrome. Ở đây cần 3 lần cắt. Các palindromes là:a | babbbab | b | ababa

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=chiều dài của str
• xác định ma trận cắt và ma trận pal từng thứ tự n x n
• for i:=0 to n, do
  • pal [i, i]:=true và cut [i, i]:=0
• đối với len trong phạm vi 2 đến n, thực hiện
  • for i trong phạm vi từ 0 đến n - len, do
    • j:=i + len - 1
    • nếu len =2, thì
    • nếu str [i] =str [j], thì pal [i, j]:=true
    • khác khi str [i] =str [j] và pal [i + 1, j-1] ≠ 0 pal [i, j]:=true
    • nếu pal [i, j] là true, thì hãy cắt [i, j]:=0
    • khác
      • cắt [i, j]:=∞
      • đối với k trong phạm vi i đến j-1, thực hiện
        • cut [i, j]:=tối thiểu cắt [i, j] và (cắt [i, k] + cắt [k + 1, j + 1] +1)
• trả về [0, n-1]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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);
}

Đầu vào

ababbbabbababa

Đầu ra

Min cuts for Palindrome Partitioning is: 3