This C++ Program Solves Palindrome Partitioning Problem.

Here is source code of the C++ Program to solve Palindrome Partitioning Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

`/*`

`* C++ Program to Solve Palindrome Partitioning Problem`

`*/`

`#include <iostream>`

`#include <cstdio>`

`#include <cstring>`

`#include <climits>`

`#include <cstring>`

`#include <cstdlib>`

using namespace std;

`// get minimum of two integers`

int min (int a, int b)

`{`

return (a < b)? a : b;

`}`

`/* Returns the minimum number of cuts needed to partition a string`

`* such that every part is a palindrome`

`*/`

int minPalPartion(char *str)

`{`

int n = strlen(str);

int C[n][n];

bool P[n][n];

int i, j, k, L;

for (i = 0; i < n; i++)

`{`

P[i][i] = true;

C[i][i] = 0;

`}`

for (L = 2; L <= n; L++)

`{`

for (i = 0; i < n - L + 1; i++)

`{`

j = i + L - 1;

if (L == 2)

P[i][j] = (str[i] == str[j]);

`else`

P[i][j] = (str[i] == str[j]) && P[i + 1][j - 1];

if (P[i][j] == true)

C[i][j] = 0;

`else`

`{`

C[i][j] = INT_MAX;

for (k = i; k <= j - 1; k++)

C[i][j] = min (C[i][j], C[i][k] + C[k + 1][j] + 1);

`}`

`}`

`}`

return C[0][n-1];

`}`

`// Main`

int main()

`{`

char str[] = "ababbbabbababa";

cout<<"Min cuts needed for Palindrome Partitioning is: "<<minPalPartion(str);

cout<<endl;

return 0;

`}`

$ g++ palindrome_partitioning.cpp $ a.out Min cuts needed for Palindrome Partitioning is: 3 ------------------ (program exited with code: 1) Press return to continue

**Sanfoundry Global Education & Learning Series – 1000 C++ Programs.**

If you wish to look at all C++ Programming examples, go to C++ Programs.