C++의 회문 분할

입력 문자열이 하나 있다고 가정하고 해당 문자열의 분할은 회문 분할이며 분할 영역의 모든 하위 문자열이 회문입니다. 이 섹션에서 우리는 주어진 문자열을 회문 분할에 필요한 최소 컷을 찾아야 합니다. 따라서 문자열이 "ababbbabbababa"와 같은 경우 회문으로 파티션을 최소로 잘라냅니다. 여기서 3컷이 필요합니다. 회문은 다음과 같습니다. 밥밥 | ㄴ | 아바바

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• n :=str의 길이
• n x n차의 절단 행렬과 pal 행렬을 정의합니다.
• i :=0에서 n에 대해
  • pal[i, i] :=true 및 cut[i, i] :=0
• 2~n 범위의 len에 대해
  • 0 ~ n – len 범위의 i에 대해
    • j :=i + len – 1
    • len =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]가 참이면 cut[i, j] :=0
    • 기타
      • 컷[i,j] :=∞
      • i ~ j-1 범위의 k에 대해
        • cut[i, j] :=cut[i, j]의 최소값 및 (cut[i, k]+ cut[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