সি++-এ সাবস্ট্রিং প্যালিনড্রোম কিনা তা যাচাই করার কোয়েরি সমাধান

সমস্যা বিবরণ

একটি স্ট্রিং str এবং Qটি কোয়েরি দেওয়া আছে। প্রতিটি কোয়েরিতে L এবং R থাকে। সাবস্ট্রিং str[L...R] প্যালিনড্রোম কিনা তা চেক করতে হবে।

উদাহরণ: str = "abccbeba", Q = 3, Queries = {{1,4}, {0,6}, {4,6}}

আউটপুট: Palindrome, Not Palindrome, Palindrome

সমাধানের পদ্ধতি

ডাইনামিক প্রোগ্রামিং (DP) পদ্ধতি:

1. DP[i][j] = true যদি str[i...j] প্যালিনড্রোম হয়।
2. বেস কেস:
   • একক ক্যারেক্টার: DP[i][i] = true
   • দুই ক্যারেক্টার: DP[i][i+1] = (str[i] == str[i+1])
3. ট্রানজিশন: DP[i][j] = (str[i] == str[j]) && DP[i+1][j-1] (যদি j-i+1 > 2)
4. প্রি-কম্পিউট করুন O(n²) সময়ে।
5. প্রতিটি কোয়েরি O(1) সময়ে উত্তর দিন।

উদাহরণ কোড

#include <bits/stdc++.h>
using namespace std;

void computeDP(int DP[][50], string str) {
    int len = str.size();
    for (int i = 0; i < len; i++)
        for (int j = 0; j < len; j++)
            DP[i][j] = 0;
    for (int j = 1; j <= len; j++) {
        for (int i = 0; i <= len - 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] = {{1,3}, {2,5}, {4,5}};
    solveAllQueries(str, Q, query);
    return 0;
}

আউটপুট

palindrome!
not palindrome!
palindrome!