C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++での回文分割

1つの入力文字列があるとします。パーティションのすべてのサブ文字列が回文である場合、その文字列の分割は回文分割です。このセクションでは、指定された文字列をパリンドロームで分割するために必要な最小限のカットを見つける必要があります。したがって、文字列が「ababbbabbababa」のような場合は、回文として分割するための最小カット。ここでは3つのカットが必要です。回文は次のとおりです。ババブ| b |アババ

これを解決するには、次の手順に従います-

  • n：=strの長さ
  • それぞれ次数nxnのカット行列とパル行列を定義します
  • for i：=0 to n、do
    • pal [i、i]：=trueおよびcut[i、i]：=0
  • 2からnの範囲のlenの場合は、
    • 0からnの範囲のiの場合– len、do
      • 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]がtrueの場合、cut [i、j]：=0
      • その他
        • cut [i、j]：=∞
        • iからj-1の範囲のkについては、
          • cut [i、j]：=最小のcut [i、j]および（cut [i、k] + cut [k + 1、j + 1] +1）
  • return cut [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

  1. C++で回文順列を作成するための最小限の削除

    問題の説明 文字列Sが与えられた場合、文字列Sの順列を回文にするために削除できる最小文字を見つける必要があります 例 str =“ abcdba”の場合、1文字に削除されます。つまり、「c」または「d」のいずれかです。 アルゴリズム 1. There can be two types of a palindrome, even length, and odd length palindromes 2. We can deduce the fact that an even length palindrome must have every character occurring even

  2. C++でのstatic_cast

    static_castは、通常/通常の型変換に使用されます。これは、暗黙的な型強制の原因となるキャストでもあり、明示的に呼び出すこともできます。 floatをintに、charをintに変換する場合などに使用する必要があります。これにより、関連する型クラスをキャストできます。 例 #include <iostream> using namespace std; int main() {    float x = 4.26;    int y = x; // C like cast    int z = static_cas