এখানে আমরা একটি শব্দকে প্যালিনড্রোম পার্টিশন করার কতগুলো উপায় আছে তা বের করার C++ প্রোগ্রাম দেখব।
এলগরিদম
Begin
শব্দটি ইনপুট নিন।
Function partitionadd(vector> &u, string &s, vector &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> &u):
vector tmp
addStrings(u, st, tmp, 0)
printSol(u) // সমাধান প্রিন্ট
return End
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
bool checkPalin(string s) { // স্ট্রিং প্যালিনড্রোম কিনা চেক
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> part) { // সমাধান প্রিন্ট
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> &u, string &s, vector &tmp, int index) {
int length = s.length();
string st;
vector curr = tmp;
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> &u) { // স্ট্রিংয়ের সব প্যালিনড্রোমিক পার্টিশন জেনারেট
vector tmp;
partitionadd(u, st, tmp, 0); // নোট: মূল কোডে addStrings কল ছিল, এখানে partitionadd কল করা হয়েছে
printSol(u);
return;
}
int main() {
string s = "tutorials";
vector> 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
