회문 분할

이 알고리즘에서 입력은 문자열이며 파티션의 모든 하위 문자열이 회문일 때 해당 문자열의 분할은 회문 분할입니다.

이 알고리즘에서 우리는 주어진 문자열을 분할하는 회문에 필요한 최소 컷을 찾아야 합니다.

입력 및 출력

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