Truy vấn kiểm tra xâu con có phải palindrome trong C++

Mô tả bài toán

Cho xâu str và Q truy vấn mỗi truy vấn là cặp L, R (chỉ số 0-based hoặc 1-based). Kiểm tra xâu con str[L..R] có phải palindrome hay không.

Ví dụ: str = "abccbeba", truy vấn {{1,4},{0,6},{4,6}} → Palindrome, Not Palindrome, Palindrome.

Giải pháp

Cách 1 (Naive): Với mỗi truy vấn, cắt xâu con và kiểm tra palindrome O(len) mỗi truy vấn.

Cách 2 (Quy hoạch động): Tiền tính bảng DP[i][j] = true nếu str[i..j] là palindrome. Xây dựng DP theo độ dài tăng dần. Truy vấn O(1).

Ví dụ minh họa (C++)

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

// Cách DP
void computeDP(bool DP[][50], string str) {
    int len = str.size();
    for (int i = 0; i < len; i++) DP[i][i] = true;
    for (int i = 0; i < len-1; i++) DP[i][i+1] = (str[i]==str[i+1]);
    for (int l = 3; l <= len; l++) {
        for (int i = 0; i+l-1 < len; i++) {
            int j = i+l-1;
            DP[i][j] = (str[i]==str[j]) && DP[i+1][j-1];
        }
    }
}

void solveAllQueries(string str, int Q, int query[][2]) {
    bool DP[50][50] = {false};
    computeDP(DP, str);
    for (int i = 0; i < Q; i++) {
        int L = query[i][0], R = query[i][1];
        if (DP[L][R]) cout << "Palindrome\n";
        else cout << "Not Palindrome\n";
    }
}

int main() {
    string str = "abccbeba";
    int Q = 3;
    int query[3][2] = {{1,3},{2,5},{4,5}}; // 0-based hoặc 1-based tùy đề
    solveAllQueries(str, Q, query);
    return 0;
}

Đầu ra

Palindrome
Not Palindrome
Palindrome