Longest Palindromic Subsequence (LPS)

Longest Palindromic Subsequence คือ subsequence ของสตริงที่เป็นพาลินโดรม และมีความยาวมากที่สุด (ต่างจาก Substring ที่ต้องติดกัน)

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

Input: "ABCDEEAB"
Output: The length of the longest palindrome subsequence is: 4
Palindrome: "AEEA" (หรือ "ABBA")

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

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

Recurrence Relation:

กำหนด L(i, j) = ความยาว LPS ใน substring str[i..j]

• ถ้า i == j: L(i, j) = 1 (ตัวเดียว)
• ถ้า str[i] == str[j] และ j == i+1: L(i, j) = 2 (คู่ติดกัน)
• ถ้า str[i] == str[j]: L(i, j) = L(i+1, j-1) + 2
• ถ้า str[i] != str[j]: L(i, j) = max(L(i, j-1), L(i+1, j))

ขั้นตอน (Bottom-up):

1. สร้างตาราง lenTable[n][n] เริ่มต้นทุกค่า = 1
2. for col = 2 ถึง n (ความยาว substring):
   • for i = 0 ถึง n-col:
     • j = i + col - 1
     • ใช้ recurrence ข้างต้นคำนวณ lenTable[i][j]
3. คืน lenTable[0][n-1]

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

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

int palSubseqLen(string str) {
    int n = str.size();
    int lenTable[n][n];

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

    // ความยาว 2 ถึง n
    for (int col = 2; col <= n; col++) {
        for (int i = 0; i < n-col+1; i++) {
            int j = i + col - 1;
            if (str[i] == str[j] && col == 2)
                lenTable[i][j] = 2;
            else if (str[i] == str[j])
                lenTable[i][j] = lenTable[i+1][j-1] + 2;
            else
                lenTable[i][j] = max(lenTable[i][j-1], lenTable[i+1][j]);
        }
    }
    return lenTable[0][n-1];
}

int main() {
    string sequence = "ABCDEEAB";
    cout << "The length of the longest palindrome subsequence is: " 
         << palSubseqLen(sequence);
    return 0;
}

Output

The length of the longest palindrome subsequence is: 4

ความซับซ้อน

• Time: O(n²)
• Space: O(n²) (ลดเป็น O(n) ได้)

ความสัมพันธ์กับ LCS

LPS ของสตริง S = LCS ของ S และ reverse(S)

ตัวอย่าง: S = "ABCDEEAB", Reverse = "BAEEDCBA" → LCS = "AEEA" (ความยาว 4)

การสร้าง LPS จริง (Reconstruction)

เดินย้อนกลับจาก lenTable[0][n-1] เหมือน LCS