Xâu con đối xứng dài nhất

Cho một chuỗi ký tự, bài toán yêu cầu tìm xâu con (substring) là palindrome (đối xứng) và có độ dài lớn nhất.

Do có nhiều bài toán con chồng chéo, quy hoạch động là phương pháp phù hợp. Ta sử dụng bảng palTab[i][j] lưu true nếu xâu con từ chỉ số i đến j là palindrome.

Đầu vào và Đầu ra

Đầu vào: Chuỗi "thisispalapsiti"
Đầu ra: Xâu con đối xứng dài nhất: "ispalapsi", độ dài = 9

Thuật toán

1. Khởi tạo bảng n x n với giá trị false.
2. Tất cả xâu con độ dài 1 là palindrome → palTab[i][i] = true.
3. Kiểm tra các xâu con độ dài 2: nếu str[i] == str[i+1] → palTab[i][i+1] = true, cập nhật maxLen = 2.
4. Với độ dài k từ 3 đến n: duyệt mọi vị trí bắt đầu i, tính j = i + k - 1. Nếu str[i] == str[j] và palTab[i+1][j-1] == true thì palTab[i][j] = true, cập nhật maxLen và start.
5. Trả về xâu con từ start độ dài maxLen.

Ví dụ C++

#include <iostream>
using namespace std;

int findLongPalSubstr(string str) {
    int n = str.size();
    bool palCheckTab[n][n];
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) palCheckTab[i][j] = false;

    int maxLength = 1;
    for (int i = 0; i < n; ++i) palCheckTab[i][i] = true;

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

    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() {
    char str[] = "thisispalapsiti";
    cout << "Length is: " << findLongPalSubstr(str);
}

Kết quả

Longest palindrome substring is: ispalapsi
Length is: 9