এই টিউটোরিয়ালে, আমাদের প্রদত্ত স্ট্রিং এর প্যালিনড্রোম সাবস্ট্রিং প্রশ্নগুলি সমাধান করতে হবে। প্যালিনড্রোম সাবস্ট্রিং প্রশ্নগুলি সমাধান করা C++ এ নিয়মিত প্রশ্নগুলি সমাধান করার চেয়ে অনেক বেশি জটিল। এর জন্য অনেক বেশি জটিল কোড এবং যুক্তি প্রয়োজন।
এই টিউটোরিয়ালে, আমাদেরকে সাবস্ট্রিং[L...R] প্রশ্নের স্ট্রিং স্ট্র এবং Q নম্বর দেওয়া হয়েছে, যার প্রতিটিতে দুটি মান L এবং R রয়েছে। আমরা এমন একটি প্রোগ্রাম লিখতে চাই যা সাবস্ট্রিং[L] কিনা তা নির্ধারণ করতে প্রশ্নগুলি সমাধান করবে। ..R] একটি প্যালিনড্রোম। আমাদের অবশ্যই সিদ্ধান্ত নিতে হবে যে L থেকে R রেঞ্জের মধ্যে গঠিত সাবস্ট্রিংটি প্রতিটি প্রশ্নের সমাধান করার জন্য একটি প্যালিনড্রোম কিনা। যেমন −
Let's input "abbbabaaaba" as our input string. The queries were [3, 13], [3, 11], [5, 8], [8, 12] It is necessary to determine whether the substring is a plaindrome A palindrome is "abaaabaaaba" (3, 13) . It is not possible to write "baaa" as a palindrome [3, 11]. As in [5, 8]: "aaab" cannot be a palindrome. There is a palindrome in "baaab" ([3, 12]).
সমাধান খোঁজার পদ্ধতি
নিষ্পাপ পদ্ধতি
এখানে, সাবস্ট্রিংটি ইনডেক্স রেঞ্জ L থেকে R পর্যন্ত কিনা তা পরীক্ষা করে আমাদের অবশ্যই একটি প্যালিনড্রোম খুঁজে বের করতে হবে। তাই, আমাদের একটি একটি করে সমস্ত সাবস্ট্রিং প্রশ্নগুলি পরীক্ষা করতে হবে এবং সেগুলি প্যালিনড্রোম কিনা তা নির্ধারণ করতে হবে। যেহেতু Q প্রশ্ন রয়েছে এবং প্রতিটি প্রশ্নের উত্তর দিতে 0(N) সময় লাগে। সবচেয়ে খারাপ ক্ষেত্রে এটি 0(Q.N) সময় নেয়।
উদাহরণ
#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] = {{3, 5}, {5, 7}, {2, 1}};
solveAllQueries(str, Q, query);
return 0;
} আউটপুট
Palindrome Palindrome Not palindrome!
ডাইনামিক প্রোগ্রামিং পদ্ধতি
সমস্যা সমাধানের জন্য একটি গতিশীল প্রোগ্রামিং পদ্ধতি ব্যবহার করা একটি দক্ষ বিকল্প। সমাধান করার জন্য, আমাদের একটি DP অ্যারে তৈরি করতে হবে, যা একটি দ্বি-মাত্রিক অ্যারে যাতে একটি বুলিয়ান মান রয়েছে যা নির্দেশ করে যে সাবস্ট্রিং [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] = {{3, 5}, {5, 7}, {2, 1}};
solveAllQueries(str, Q, query);
return 0;
} আউটপুট
palindrome! not palindrome! palindrome!
উপসংহার
এই টিউটোরিয়ালে, আমরা শিখেছি কিভাবে c++ কোড সহ প্যালিনড্রোম সাবস্ট্রিং কোয়েরি সমাধান করতে হয়। আমরা জাভা, পাইথন এবং অন্যান্য ভাষায় এই কোডটি লিখতে পারি। এই কোডটি ছিল সবচেয়ে জটিল এবং দীর্ঘ কোডগুলির একটি। প্যালিনড্রোম কোয়েরিগুলি নিয়মিত সাবস্ট্রিং কোয়েরির চেয়ে কঠিন, এবং তাদের খুব সঠিক যুক্তি প্রয়োজন। আমরা আশা করি আপনার এই টিউটোরিয়ালটি সহায়ক হবে৷
