fork download
copy 
  1. #include<bits/stdc++.h>
  2. //zone
  3. //the joy you feel when you draw out 120 % of your potential :D
  4. using namespace std;
  5. int mincut(string str)
  6. {
  7.     int n = str.length();
  8.     bool P[n][n];//for checking of pallindrome validation from i to j - 1
  9.     int c[n];
  10.     int i,j;
  11.     for(i = 0 ; i < n ; i++)
  12.     {
  13.         P[i][i] = true; // single word is itself a pallindrome
  14.     }
  15.     int L;
  16.     for(L = 2 ; L <=n ; L++)//checking for pallindromes for varying lengths of substring
  17.     {
  18.         for(i = 0 ; i < n - L + 1 ; i++)
  19.         {
  20.             j = i + L - 1; //ending index of substring
  21.             if(L == 2)
  22.             {
  23.                 if(str[i] == str[j])
  24.                 {
  25.                     P[i][j] = true;
  26.                 }
  27.                 else
  28.                     P[i][j] = false;
  29.             }
  30.             else
  31.             {// this means that if str[i] == str[j] and if all the characters within its are pallindrome
  32.             // than P[i][j] is pallindrome suppose for P[2][5] to be pallindrome then it is must for P[3][4]
  33.             //to be pallindrome and S[2] == S[5]
  34.                 if(str[i] == str[j] && P[i + 1][j - 1] == true)
  35.                 {
  36.                     P[i][j] = true;
  37.                 }
  38.                 else
  39.                     P[i][j] = false;
  40.             }
  41.         }
  42.     }
  43.     //now we will starting checking for cuts
  44.     for(i = 0 ; i  < n ; i++)
  45.     {
  46.         if(P[0][i] == true) //if pallindrome 0 to i is true then pallindrome from 0 to i requires 0 mincuts
  47.         {
  48.             c[i] = 0;
  49.         }
  50.         else
  51.         {
  52.             c[i] = INT_MAX;
  53.             for(j = 0 ; j < i ; j++) // iterate over for all possibilities for cuts for substring 0 to i
  54.             {
  55.                 if(P[j + 1][i] == true)
  56.                 {
  57.                     c[i] = min(c[i],1+c[j]);
  58.                 }
  59.             }
  60.         }
  61.     }
  62.     return c[n-1]; // return total mincuts for 0 to n-1 length
  63. }
  64. int main()
  65. {
  66.     string s;
  67.     cin >> s;
  68.     cout<<"Mincuts required\n";
  69.     cout<<mincut(s)<<endl;
  70.     return 0;
  71. }
  72.  
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
abababaa
stdout
copy 
Mincuts required
1
https://ideone.com/yGbzNB
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!