หา Substring แบบพาลินโดรมที่ยาวที่สุด

ในสตริงที่กำหนด เราต้องการหา substring ที่เป็นพาลินโดรม (อ่านจากหน้าหลังได้เหมือนกัน) และมีความยาวมากที่สุด

ปัญหานี้มี subproblems ที่ทับซ้อนกัน (Overlapping Subproblems) ทำให้ Dynamic Programming เหมาะสม เราสามารถใช้ตาราง 2 มิติเก็บผลลัพธ์ของ subproblems ไว้ เพื่อนำไปใช้ต่อโดยไม่ต้องคำนวณซ้ำ

ตัวอย่าง Input และ Output

Input: "thisispalapsiti"
Output: Longest palindrome substring is: ispalapsi
Length is: 9

อัลกอริทึม Dynamic Programming

ฟังก์ชัน findLongPalSubstr(str)

ขั้นตอน:

1. สร้างตาราง palTab[n][n] เก็บ boolean (true = เป็นพาลินโดรม)
2. เติมค่า false ทั้งตาราง
3. ความยาว 1: ตัวอักษรเดี่ยวทุกตัวเป็นพาลินโดรม → palTab[i][i] = true
4. ความยาว 2: ตรวจสอบคู่ที่อยู่ติดกัน str[i] == str[i+1] → palTab[i][i+1] = true
5. ความยาว 3 ถึง n: สำหรับความยาว k = 3 ถึง n
   • substring จาก i ถึง j (j = i + k - 1)
   • เป็นพาลินโดรมถ้า str[i] == str[j] และ palTab[i+1][j-1] == true
   • อัปเดต maxLen และ start เมื่อเจอพาลินโดรมที่ยาวกว่า
6. คืนค่า substring จาก start ความยาว maxLen

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

#include <iostream>
#include <string>
using namespace std;

int findLongPalSubstr(string str) {
    int n = str.size();
    bool palCheckTab[n][n];
    
    // เริ่มต้นทั้งหมดเป็น false
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            palCheckTab[i][j] = false;

    int maxLength = 1;
    // ความยาว 1
    for (int i = 0; i < n; ++i)
        palCheckTab[i][i] = true;

    int start = 0;
    // ความยาว 2
    for (int i = 0; i < n-1; ++i) {
        if (str[i] == str[i+1]) {
            palCheckTab[i][i+1] = true;
            start = i;
            maxLength = 2;
        }
    }

    // ความยาว 3 ถึง n
    for (int k = 3; k <= n; ++k) {
        for (int i = 0; i < n-k+1; ++i) {
            int j = i + k - 1;
            if (palCheckTab[i+1][j-1] && str[i] == str[j]) {
                palCheckTab[i][j] = true;
                if (k > maxLength) {
                    start = i;
                    maxLength = k;
                }
            }
        }
    }

    cout << "Longest palindrome substring is: " 
         << str.substr(start, maxLength) << endl;
    return maxLength;
}

int main() {
    string str = "thisispalapsiti";
    cout << "Length is: " << findLongPalSubstr(str);
    return 0;
}

Output

Longest palindrome substring is: ispalapsi
Length is: 9

ความซับซ้อน

• Time: O(n²) - วนลูป 2 ชั้น
• Space: O(n²) - ตาราง n×n

หมายเหตุ

ยังมีวิธี Expand Around Center ที่ใช้ Space O(1) และ Manacher's Algorithm ที่เป็น O(n) แต่ DP นี้เข้าใจง่ายและเพียงพอสำหรับ n ปานกลาง