এই টিউটোরিয়ালে দেওয়া স্ট্রিং-এর প্যালিনড্রোম সাবস্ট্রিং কোয়েরি সমাধান করতে হবে। সাধারণ কোয়েরির চেয়ে এটি অনেক বেশি জটিল এবং জটিল লজিক ও কোড দরকার।
স্ট্রিং str এবং Q সংখ্যক সাবস্ট্রিং [L...R] কোয়েরি দেওয়া আছে, প্রতিটিতে L এবং R ভ্যালু আছে। প্রোগ্রাম লিখতে হবে যা প্রতিটি কোয়েরির জন্য সাবস্ট্রিং [L...R] প্যালিনড্রোম কিনা তা নির্ণয় করবে।
সমাধানের পদ্ধতি
নেইভ মেথড (Naive Method)
প্রতিটি কোয়েরির জন্য সাবস্ট্রিং এক্সট্রাক্ট করে প্যালিনড্রোম কিনা চেক করুন। Q কোয়েরি এবং প্রতিটি O(N) সময় নেয়, মোট O(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;
}
}
return flag == 1 ? 1 : 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] - query[i][0] + 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, 4}};
solveAllQueries(str, Q, query);
return 0;
}
আউটপুট
Palindrome Palindrome Not palindrome!
ডাইনামিক প্রোগ্রামিং পদ্ধতি
DP[i][j] = true হলে সাবস্ট্রিং i থেকে j প্যালিনড্রোম। DP টেবিল বানানোর পর প্রতিটি কোয়েরি O(1)-এ উত্তর দেওয়া যায়।
উদাহরণ ২ (DP)
#include <bits/stdc++.h>
using namespace std;
void computeDP(int DP[][50], string str) {
int length = str.size();
for (int i = 0; i < length; i++)
for (int j = 0; j < length; j++)
DP[i][j] = 0;
for (int j = 1; j <= length; j++) {
for (int 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 << "palindrome!\n" : cout << "not palindrome!\n";
}
}
int main() {
string str = "abccbeba";
int Q = 3;
int query[Q][2] = {{3, 5}, {5, 7}, {2, 4}};
solveAllQueries(str, Q, query);
return 0;
}
আউটপুট
palindrome! not palindrome! palindrome!
উপসংহার
প্যালিনড্রোম সাবস্ট্রিং কোয়েরি সমাধানের দুটি পদ্ধতি (নেইভ এবং DP) দেখানো হয়েছে। DP পদ্ধতিটি বড় ইনপুটের জন্য দক্ষ।
