এখানে আমরা একটি C++ প্রোগ্রাম নিয়ে আলোচনা করব যাতে একটি শব্দকে পার্টিশন করার জন্য কতগুলো উপায় বের করা যায় যাতে প্রতিটি শব্দ একটি প্যালিনড্রোম হয়।
অ্যালগরিদম
Begin Take the word as input. Function partitionadd(vector<vector<string> > &u, string &s, vector<string> &tmp, int index): if (index == 0) tmp.clear() for i = index to length-1 st = st + s[i] if (checkPalin(st)) tmp.push_back(st) if (i+1 < length) partitionadd(u, s, tmp, i+1) else u.push_back(tmp) tmp = curr return End Begin Function partition(string st, vector<vector<string> >&u): vector<string> tmp addStrings(u, st, tmp, 0) printSol(u) //to print the solution return End
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
bool checkPalin(string s) { //check if string is palindrome or not.
int length = s.length();
length--;
for (int i=0; i<length; i++) {
if (s[i] != s[length])
return false;
length--;
}
return true;
}
void printSol(vector<vector<string> > part) { //print the solution
for (int i = 0; i < part.size(); ++i) {
for(int j = 0; j < part[i].size(); ++j)
cout << part[i][j] << " ";
cout << endl;
}
return;
}
void partitionadd(vector<vector<string> > &u, string &s, vector<string> &tmp, int index) {
int length = s.length(); //store length of the string
string st;
vector<string> curr = tmp;
// goes through all indexes and recursively add remaining partitions if current string is palindrome.
if (index == 0)
tmp.clear();
for (int i = index; i < length; ++i) {
st = st + s[i];
if (checkPalin(st)) {
tmp.push_back(st);
if (i+1 < length)
partitionadd(u,s,tmp,i+1);
else
u.push_back(tmp);
tmp = curr;
}
}
return;
}
void partition(string st, vector<vector<string> >&u) //generate all palindromic partitions of 'str' and stores the result in 'm'. {
vector<string> tmp;
addStrings(u, st, tmp, 0);
printSol(u);
return;
}
int main() {
string s = "tutorials";
vector<vector<string> > part;
cout<<"the number of partitions:"<<endl;
partition(s, part);
return 0;
} আউটপুট
the number of partitions: t u t o r i a l s tut o r i a l s
