โปรแกรมตรวจสอบว่าส่วนย่อยสตริงเป็นพาลินโดรมด้วยคำถามหลายคำถามใน C++

ให้สตริง str และ Q คำถาม แต่ละคำถามมี L, R ต้องการตรวจสอบว่า substring[L..R] เป็นพาลินโดรมหรือไม่

ตัวอย่าง: str = "abccbeba", Q=3, queries = {{1,4},{0,6},{4,6}} [1,4]="bccb"→Palindrome, [0,6]="abccbeb"→Not, [4,6]="beb"→Palindrome

วิธีแก้ปัญหา

วิธีง่าย (Naive): ตรวจสอบแต่ละคำถามแยกกัน O(N) ต่อคำถาม

วิธีมีประสิทธิภาพ: Dynamic Programming O(N²) Preprocess, O(1) ต่อคำถาม

สร้างตาราง DP[n][n] โดย DP[i][j] = true ถ้า str[i..j] เป็นพาลินโดรม DP[i][j] = (str[i]==str[j]) และ (j-i<=2 หรือ DP[i+1][j-1])

ตัวอย่างโค้ด C++ (DP)

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

void computeDP(bool DP[][50], string str) {
    int len = str.size();
    for (int j = 1; j <= len; j++) {
        for (int i = 0; i <= len-j; i++) {
            if (j <= 2)
                DP[i][i+j-1] = (str[i] == str[i+j-1]);
            else
                DP[i][i+j-1] = (str[i] == str[i+j-1]) && DP[i+1][i+j-2];
        }
    }
}

void solveAllQueries(string str, int Q, int query[][2]) {
    bool DP[50][50] = {};
    computeDP(DP, str);
    for (int i = 0; i < Q; i++) {
        cout << (DP[query[i][0]-1][query[i][1]-1] ? "Palindrome" : "Not Palindrome") << endl;
    }
}

int main() {
    string str = "abccbeba";
    int Q = 3;
    int query[3][2] = {{1,3},{2,5},{4,5}};
    solveAllQueries(str, Q, query);
    return 0;
}

เอาต์พุต

Palindrome
Not Palindrome
Palindrome