Phân vùng Palindrome

Trong thuật toán này, đầu vào là một chuỗi, 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 thuật toán này, chúng ta phải tìm ra những đường cắt tối thiểu cần thiết để phân vùng palindrome cho chuỗi đã cho.

Đầu vào và Đầu ra

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

Thuật toán

minPalPart(str)

Đầu vào: Chuỗi đã cho.

Đầu ra: Số lượng phân vùng palindromic tối thiểu từ chuỗi.

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

Ví dụ

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

Đầu ra

Min cuts for Palindrome Partitioning is: 3