এই সমস্যায়, আমাদেরকে স্ট্রিং str, Q নম্বর দেওয়া হয়েছে প্রতিটি সাবস্ট্রিং [L...R]-এর জন্য L এবং R দুটি মান নিয়ে গঠিত। আমাদের কাজ হল সাবস্ট্রিং[L…R] প্যালিনড্রোম কিনা তা পরীক্ষা করার জন্য প্রশ্নের সমাধান করার জন্য একটি প্রোগ্রাম তৈরি করা।
সমস্যা বর্ণনা − প্রতিটি প্রশ্নের সমাধানের জন্য, L থেকে R রেঞ্জের মধ্যে তৈরি করা সাবস্ট্রিংটি প্যালিনড্রোম কিনা তা আমাদের পরীক্ষা করতে হবে৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
str = “abccbeba” , Q = 3
Query[][] = {{1, 4}, {0, 6}, {4, 6}} আউটপুট
Palindrome Not Palindrome Palindrome
ব্যাখ্যা
Creating all substring for the given substrings : Substring[1...4] = “bccb”, it is a palindrome Substring[0...6] = “abccbeb”, it is a not palindrome Substring[4...6] = “beb”, it is a palindrome
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল প্রতিটি প্রশ্নের সমাধান করা। এটি সমাধান করার জন্য, আমাদের সূচক পরিসীমা L থেকে R পর্যন্ত সাবস্ট্রিং খুঁজে বের করতে হবে। এবং সাবস্ট্রিংটি প্যালিনড্রোম কিনা তা পরীক্ষা করে দেখতে হবে।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int isPallindrome(string str){
int i, length;
int flag = 0;
length = str.length();
for(i=0;i < length ;i++){
if(str[i] != str[length-i-1]) {
flag = 1; break;
}
}
if (flag==1)
return 1;
return 0;
}
void solveAllQueries(string str, int Q, int query[][2]){
for(int i = 0; i < Q; i++){ isPallindrome(str.substr(query[i][0] - 1, query[i][1] - 1))?cout<<"Palindrome\n":cout<<"Not palindrome!\n";
}
}
int main() {
string str = "abccbeba"; int Q = 3;
int query[Q][2] = {{1, 3}, {2, 5}, {4, 5}};
solveAllQueries(str, Q, query);
return 0;
} আউটপুট
Palindrome Not palindrome! Palindrome
এটি একটি নিরীহ পদ্ধতি কিন্তু একটি কার্যকরী নয়৷
৷সমস্যাটির একটি দক্ষ সমাধান হল গতিশীল প্রোগ্রামিং পদ্ধতি ব্যবহার করা। সমাধানের জন্য, আমাদের একটি DP অ্যারে তৈরি করতে হবে একটি 2-D অ্যারে যা একটি বুলিয়ান মান সঞ্চয় করে যা বোঝায় যে সাবস্ট্রিং[i...j] DP[i][j] এর জন্য একটি প্যালিনড্রোম কিনা।
আমরা এই DP ম্যাট্রিক্স তৈরি করব এবং প্রতিটি প্রশ্নের সমস্ত L-R মান পরীক্ষা করব।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void computeDP(int DP[][50], string str){
int length = str.size();
int i, j;
for (i = 0; i < length; i++) {
for (j = 0; j < length; j++)
DP[i][j] = 0;
}
for (j = 1; j <= length; j++) {
for (i = 0; i <= length - j; i++) {
if (j <= 2) {
if (str[i] == str[i + j - 1])
DP[i][i + j - 1] = 1;
}
else if (str[i] == str[i + j - 1])
DP[i][i + j - 1] = DP[i + 1][i + j - 2];
}
}
}
void solveAllQueries(string str, int Q, int query[][2]){
int DP[50][50];
computeDP(DP, str);
for(int i = 0; i < Q; i++){
DP[query[i][0] - 1][query[i][1] - 1]?cout<<"not palindrome!\n":cout<<"palindrome!\n";
}
}
int main() {
string str = "abccbeba"; int Q = 3;
int query[Q][2] = {{1, 3}, {2, 5}, {4, 5}};
solveAllQueries(str, Q, query);
return 0;
} আউটপুট
palindrome! not palindrome! palindrome!
