Khóa học CTDL và GT

Bài 10.4. Palindrome và các bài toán liên quan

Chào mừng các bạn quay trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ cùng nhau khám phá một khái niệm khá thú vị và phổ biến trong cả lý thuyết lẫn thực tế lập trình: Palindrome.

Palindrome là gì? Đơn giản là một chuỗi ký tự (hoặc một số, một câu,...) mà khi chúng ta đọc xuôi hay đọc ngược, kết quả nhận được là như nhau. Nghe có vẻ đơn giản, nhưng các bài toán liên quan đến Palindrome lại xuất hiện khá thường xuyên trong các cuộc phỏng vấn code, các kỳ thi lập trình và cả trong các ứng dụng thực tế (như xử lý chuỗi, sinh học, mật mã học).

Trong bài viết này, chúng ta sẽ đi sâu vào:

• Kiểm tra xem một chuỗi có phải là Palindrome hay không bằng các cách khác nhau.
• Mở rộng bài toán kiểm tra Palindrome với các điều kiện phức tạp hơn (bỏ qua khoảng trắng, ký tự đặc biệt, không phân biệt hoa thường).
• Kiểm tra Palindrome với các loại dữ liệu khác như số nguyên.
• Tìm hiểu một trong những bài toán Palindrome "kinh điển": tìm Palindrome con dài nhất trong một chuỗi.

Tất cả sẽ được minh họa bằng mã nguồn C++ chi tiết và dễ hiểu!

Palindrome Cơ Bản: Kiểm tra một chuỗi

Bài toán cơ bản nhất là kiểm tra xem một chuỗi cho trước có phải là Palindrome hay không. Ví dụ: "madam", "level", "racecar" là Palindrome, còn "hello", "world" thì không.

Cách tiếp cận đơn giản nhất là đảo ngược chuỗi gốc và so sánh với chính nó. Nếu hai chuỗi giống nhau, đó là Palindrome.

#include <iostream>
#include <string>
#include <algorithm> // Để sử dụng std::reverse

bool isPalindromeSimple(const std::string& s) {
    std::string reversed_s = s;
    std::reverse(reversed_s.begin(), reversed_s.end());
    return s == reversed_s;
}

int main() {
    std::string str1 = "madam";
    std::string str2 = "hello";

    std::cout << "\"" << str1 << "\" is palindrome? " << (isPalindromeSimple(str1) ? "Yes" : "No") << std::endl;
    std::cout << "\"" << str2 << "\" is palindrome? " << (isPalindromeSimple(str2) ? "Yes" : "No") << std::endl;

    return 0;
}

Giải thích mã:

• Hàm isPalindromeSimple nhận một chuỗi s làm đầu vào.
• Chúng ta tạo một bản sao reversed_s của chuỗi gốc.
• Hàm std::reverse từ thư viện <algorithm> được sử dụng để đảo ngược bản sao này.
• Cuối cùng, chúng ta so sánh chuỗi gốc s với chuỗi đã đảo ngược reversed_s. Nếu chúng bằng nhau, hàm trả về true, ngược lại trả về false.

Cách này dễ hiểu, nhưng nó tạo ra một chuỗi mới, tốn thêm bộ nhớ (độ phức tạp không gian O(N), với N là độ dài chuỗi) và việc đảo ngược cũng mất thời gian tương ứng (độ phức tạp thời gian O(N)).

Có cách nào hiệu quả hơn, không cần tạo chuỗi mới không? Có, chúng ta sử dụng kỹ thuật Two Pointers (Hai con trỏ).

Ý tưởng là sử dụng hai con trỏ, một con trỏ left bắt đầu từ đầu chuỗi (index 0) và một con trỏ right bắt đầu từ cuối chuỗi (index length - 1). Chúng ta di chuyển con trỏ left tiến về phía trước và con trỏ right lùi về phía sau, đồng thời so sánh ký tự tại vị trí của hai con trỏ.

• Nếu ký tự tại s[left] khác với s[right] tại bất kỳ thời điểm nào, chuỗi đó không phải là Palindrome.
• Nếu chúng ta duyệt qua toàn bộ chuỗi (khi left gặp hoặc vượt qua right) mà không tìm thấy cặp ký tự nào khác nhau, thì chuỗi đó là Palindrome.

#include <iostream>
#include <string>

bool isPalindromeTwoPointers(const std::string& s) {
    int left = 0;
    int right = s.length() - 1;

    while (left < right) {
        // So sánh ký tự tại hai con trỏ
        if (s[left] != s[right]) {
            return false; // Không phải Palindrome
        }
        // Di chuyển con trỏ vào trong
        left++;
        right--;
    }

    // Nếu vòng lặp kết thúc mà không tìm thấy cặp khác nhau nào
    return true; // Là Palindrome
}

int main() {
    std::string str1 = "madam";
    std::string str2 = "hello";
    std::string str3 = "a";     // Chuỗi 1 ký tự cũng là Palindrome
    std::string str4 = "";      // Chuỗi rỗng cũng được coi là Palindrome

    std::cout << "\"" << str1 << "\" is palindrome? " << (isPalindromeTwoPointers(str1) ? "Yes" : "No") << std::endl;
    std::cout << "\"" << str2 << "\" is palindrome? " << (isPalindromeTwoPointers(str2) ? "Yes" : "No") << std::endl;
    std::cout << "\"" << str3 << "\" is palindrome? " << (isPalindromeTwoPointers(str3) ? "Yes" : "No") << std::endl;
    std::cout << "\"" << str4 << "\" is palindrome? " << (isPalindromeTwoPointers(str4) ? "Yes" : "No") << std::endl;

    return 0;
}

Giải thích mã:

• Hàm isPalindromeTwoPointers sử dụng hai biến left và right làm chỉ số.
• Vòng lặp while (left < right) tiếp tục cho đến khi hai con trỏ gặp nhau hoặc vượt qua nhau.
• Bên trong vòng lặp, s[left] được so sánh với s[right].
• Nếu chúng khác nhau, hàm ngay lập tức trả về false.
• Nếu chúng bằng nhau, left tăng lên và right giảm xuống để kiểm tra cặp ký tự tiếp theo.
• Nếu vòng lặp kết thúc (tức là tất cả các cặp đã được kiểm tra và đều bằng nhau), hàm trả về true.

Phương pháp này có độ phức tạp thời gian O(N) vì chúng ta chỉ duyệt qua một nửa chuỗi và độ phức tạp không gian O(1) vì chúng ta chỉ sử dụng một vài biến con trỏ mà không tạo cấu trúc dữ liệu mới. Đây là cách hiệu quả nhất để kiểm tra Palindrome cơ bản.

Palindrome Nâng Cao: Bỏ qua Ký tự đặc biệt và Không phân biệt Hoa thường

Trong thực tế, định nghĩa Palindrome có thể "mềm dẻo" hơn. Chẳng hạn, câu "A man, a plan, a canal: Panama" được coi là một Palindrome khi chúng ta bỏ qua các dấu câu, khoảng trắng và không phân biệt chữ hoa chữ thường.

Để giải quyết bài toán này, chúng ta cần thêm bước tiền xử lý hoặc xử lý "trực tiếp" trong quá trình duyệt. Ý tưởng là khi di chuyển hai con trỏ left và right, chúng ta sẽ bỏ qua các ký tự không phải là chữ cái hoặc số. Đồng thời, khi so sánh, chúng ta sẽ chuyển cả hai ký tự về cùng một dạng (ví dụ: chữ thường) trước khi so sánh.

#include <iostream>
#include <string>
#include <cctype> // Để sử dụng isalnum, tolower

bool isPalindromeStrict(const std::string& s) {
    int left = 0;
    int right = s.length() - 1;

    while (left < right) {
        // Di chuyển con trỏ left qua các ký tự không phải chữ cái hoặc số
        while (left < right && !std::isalnum(s[left])) {
            left++;
        }
        // Di chuyển con trỏ right qua các ký tự không phải chữ cái hoặc số
        while (left < right && !std::isalnum(s[right])) {
            right--;
        }

        // Nếu sau khi di chuyển, left vẫn nhỏ hơn right (chưa gặp nhau hoặc vượt qua)
        // thì so sánh ký tự hiện tại (đã được bỏ qua ký tự đặc biệt)
        if (left < right) {
            // So sánh ký tự, chuyển về chữ thường trước khi so sánh
            if (std::tolower(s[left]) != std::tolower(s[right])) {
                return false; // Không phải Palindrome
            }
            // Di chuyển con trỏ vào trong
            left++;
            right--;
        }
    }

    // Nếu vòng lặp kết thúc mà không tìm thấy cặp khác nhau nào
    return true; // Là Palindrome
}

int main() {
    std::string str1 = "A man, a plan, a canal: Panama"; // Expected: True
    std::string str2 = "race a car";                     // Expected: False
    std::string str3 = " ";                              // Expected: True (sau khi bỏ qua khoảng trắng)
    std::string str4 = ".,";                             // Expected: True (sau khi bỏ qua ký tự đặc biệt)
    std::string str5 = "OP";                             // Expected: False

    std::cout << "\"" << str1 << "\" is palindrome (strict)? " << (isPalindromeStrict(str1) ? "Yes" : "No") << std::endl;
    std::cout << "\"" << str2 << "\" is palindrome (strict)? " << (isPalindromeStrict(str2) ? "Yes" : "No") << std::endl;
    std::cout << "\"" << str3 << "\" is palindrome (strict)? " << (isPalindromeStrict(str3) ? "Yes" : "No") << std::endl;
    std::cout << "\"" << str4 << "\" is palindrome (strict)? " << (isPalindromeStrict(str4) ? "Yes" : "No") << std::endl;
    std::cout << "\"" << str5 << "\" is palindrome (strict)? " << (isPalindromeStrict(str5) ? "Yes" : "No") << std::endl;

    return 0;
}

Giải thích mã:

• Chúng ta vẫn sử dụng hai con trỏ left và right.
• Trước khi so sánh, chúng ta có hai vòng lặp while lồng bên trong:
  • Vòng lặp đầu tiên di chuyển left tiến lên cho đến khi nó gặp một ký tự là chữ cái hoặc số (std::isalnum(s[left])).
  • Vòng lặp thứ hai di chuyển right lùi xuống cho đến khi nó gặp một ký tự là chữ cái hoặc số (std::isalnum(s[right])).
  • Điều kiện left < right trong các vòng lặp này là quan trọng để tránh việc con trỏ đi ra ngoài phạm vi nếu chuỗi chỉ chứa toàn ký tự đặc biệt hoặc rỗng.
• Sau khi di chuyển con trỏ, chúng ta kiểm tra lại left < right. Nếu điều này còn đúng, tức là chúng ta đã tìm thấy hai ký tự hợp lệ để so sánh.
• Chúng ta sử dụng std::tolower để chuyển cả hai ký tự về dạng chữ thường trước khi so sánh, đảm bảo tính không phân biệt hoa thường.
• Nếu std::tolower(s[left]) khác std::tolower(s[right]), hàm trả về false.
• Nếu chúng bằng nhau, left và right tiếp tục di chuyển vào trong.
• Nếu vòng lặp while (left < right) chính kết thúc, nghĩa là chuỗi đã được kiểm tra và là Palindrome.

Phương pháp này vẫn giữ nguyên độ phức tạp thời gian O(N) vì mỗi ký tự chỉ được duyệt qua tối đa hai lần và độ phức tạp không gian O(1).

Palindrome Số: Kiểm tra một số có phải là Palindrome?

Palindrome không chỉ giới hạn ở chuỗi ký tự. Một số nguyên cũng có thể là Palindrome nếu đọc xuôi và ngược giống nhau. Ví dụ: 121, 1331, 9 là Palindrome, còn 123, 10, -121 thì không.

Bài toán này có thể giải bằng cách chuyển số thành chuỗi và áp dụng phương pháp kiểm tra chuỗi Palindrome đã học. Tuy nhiên, một cách tiếp cận khác là xử lý trực tiếp với các phép toán số học, tránh việc chuyển đổi kiểu dữ liệu.

Ý tưởng là "đảo ngược" một nửa của số và so sánh với nửa còn lại.

• Các số âm không thể là Palindrome (trừ một số trường hợp đặc biệt tùy định nghĩa, nhưng thường thì không).
• Các số dương kết thúc bằng 0 (ví dụ: 120, 30) không thể là Palindrome (trừ số 0). Lý do là số Palindrome đảo ngược của chúng sẽ bắt đầu bằng 0, điều này không thể xảy ra với số gốc (vì số gốc không bắt đầu bằng 0, trừ số 0).

Chúng ta sẽ xây dựng một số mới bằng cách lấy các chữ số từ cuối số gốc và ghép chúng vào số mới theo thứ tự ngược lại. Chúng ta dừng lại khi số gốc nhỏ hơn hoặc bằng số mới được xây dựng.

#include <iostream>

bool isPalindromeNumber(int x) {
    // 1. Xử lý các trường hợp đặc biệt
    // Số âm không phải là Palindrome
    if (x < 0) {
        return false;
    }
    // Số kết thúc bằng 0 (trừ số 0) không phải là Palindrome
    if (x % 10 == 0 && x != 0) {
        return false;
    }

    // 2. Xây dựng số đảo ngược
    int reversed_num = 0;
    // Chúng ta chỉ cần đảo ngược đến khi reversed_num lớn hơn hoặc bằng nửa số gốc
    while (x > reversed_num) {
        // Lấy chữ số cuối cùng của x và thêm vào reversed_num
        reversed_num = reversed_num * 10 + x % 10;
        // Loại bỏ chữ số cuối cùng khỏi x
        x /= 10;
    }

    // 3. So sánh số gốc và số đảo ngược
    // Nếu số gốc có số chữ số chẵn, Palindrome khi x == reversed_num
    // Nếu số gốc có số chữ số lẻ, chữ số ở giữa sẽ nằm trong reversed_num (ở hàng đơn vị).
    // Chúng ta cần loại bỏ chữ số giữa này khỏi reversed_num bằng cách chia lấy nguyên cho 10
    // và so sánh x với reversed_num / 10
    return x == reversed_num || x == reversed_num / 10;
}

int main() {
    int num1 = 121;     // Expected: True
    int num2 = -121;    // Expected: False
    int num3 = 10;      // Expected: False
    int num4 = 12345;   // Expected: False
    int num5 = 1221;    // Expected: True
    int num6 = 0;       // Expected: True

    std::cout << num1 << " is palindrome? " << (isPalindromeNumber(num1) ? "Yes" : "No") << std::endl;
    std::cout << num2 << " is palindrome? " << (isPalindromeNumber(num2) ? "Yes" : "No") << std::endl;
    std::cout << num3 << " is palindrome? " << (isPalindromeNumber(num3) ? "Yes" : "No") << std::endl;
    std::cout << num4 << " is palindrome? " << (isPalindromeNumber(num4) ? "Yes" : "No") << std::endl;
    std::cout << num5 << " is palindrome? " << (isPalindromeNumber(num5) ? "Yes" : "No") << std::endl;
    std::cout << num6 << " is palindrome? " << (isPalindromeNumber(num6) ? "Yes" : "No") << std::endl;

    return 0;
}

Giải thích mã:

• Các trường hợp đặc biệt (số âm, số dương kết thúc bằng 0) được xử lý trước.
• Chúng ta sử dụng vòng lặp while (x > reversed_num) để xây dựng số đảo ngược.
  • x % 10 lấy chữ số cuối cùng của x.
  • reversed_num = reversed_num * 10 + x % 10 thêm chữ số này vào cuối reversed_num.
  • x /= 10 loại bỏ chữ số cuối cùng khỏi x.
• Vòng lặp dừng lại khi x (phần còn lại của số gốc) nhỏ hơn hoặc bằng reversed_num (số được đảo ngược). Tại điểm này, chúng ta đã "chia đôi" số gốc một cách hiệu quả.
• Sau vòng lặp:
  • Nếu số gốc có số chữ số chẵn, x sẽ bằng reversed_num nếu nó là Palindrome (ví dụ: 1221 -> x = 12, reversed_num = 12).
  • Nếu số gốc có số chữ số lẻ, x sẽ nhỏ hơn reversed_num và chữ số ở giữa sẽ nằm ở hàng đơn vị của reversed_num. Chúng ta cần loại bỏ chữ số giữa này bằng cách chia reversed_num cho 10 (reversed_num / 10) và so sánh với x (ví dụ: 121 -> x = 1, reversed_num = 12 -> vòng lặp tiếp: x = 1, reversed_num = 12*10+1 = 121 -> x không còn > reversed_num -> vòng lặp dừng. So sánh x=1 với reversed_num=121/10 = 12 (sai); So sánh x=1 với reversed_num/10 = 121/10 = 12 (sai) - chờ chút, có lỗi logic ở ví dụ 121.
  • Sửa lại logic ví dụ 121:
    • x = 121, reversed_num = 0
    • Vòng 1: x=121 > reversed_num=0. reversed_num = 0*10 + 121%10 = 1. x = 121/10 = 12.
    • Vòng 2: x=12 > reversed_num=1. reversed_num = 1*10 + 12%10 = 10 + 2 = 12. x = 12/10 = 1.
    • Vòng 3: x=1 KHÔNG > reversed_num=12. Vòng lặp dừng.
    • Kết quả: x=1, reversed_num=12.
    • Kiểm tra: x == reversed_num (1 == 12) -> Sai.
    • Kiểm tra: x == reversed_num / 10 (1 == 12 / 10 = 1) -> Đúng.
  • Vậy, kết quả cuối cùng là Palindrome nếu x == reversed_num (cho số chữ số chẵn) HOẶC x == reversed_num / 10 (cho số chữ số lẻ).

Phương pháp này có độ phức tạp thời gian O(log N) vì số lần lặp bằng với số chữ số của N, và độ phức tạp không gian O(1).

Các Bài toán Palindrome Liên Quan Phức tạp hơn

Ngoài việc kiểm tra, Palindrome còn là nền tảng cho nhiều bài toán khác trong lập trình thi đấu và thực tế. Một trong những bài toán nổi tiếng nhất là:

Tìm Palindrome con dài nhất (Longest Palindromic Substring)

Bài toán này yêu cầu tìm chuỗi con (substring - tức là một đoạn liên tục các ký tự trong chuỗi gốc) là Palindrome và có độ dài lớn nhất.

Ví dụ:

• Trong chuỗi "babad", các Palindrome con là "b", "a", "bab", "aba", "d". Palindrome con dài nhất là "bab" hoặc "aba".
• Trong chuỗi "cbbd", các Palindrome con là "c", "b", "bb", "d". Palindrome con dài nhất là "bb".

Có nhiều thuật toán để giải quyết bài toán này, bao gồm Quy hoạch động (Dynamic Programming) với độ phức tạp O(N^2), hoặc thuật toán Manacher với độ phức tạp tối ưu O(N). Tuy nhiên, thuật toán "Expand Around Center" (Mở rộng quanh trung tâm) thường được sử dụng vì nó tương đối dễ hiểu và triển khai, với độ phức tạp O(N^2).

Ý tưởng của "Expand Around Center": Một Palindrome luôn có một "trung tâm". Trung tâm này có thể là:

1. Một ký tự duy nhất (đối với Palindrome có độ dài lẻ, ví dụ: "aba" có trung tâm là 'b').
2. Khoảng trống giữa hai ký tự giống nhau (đối với Palindrome có độ dài chẵn, ví dụ: "abba" có trung tâm là khoảng trống giữa hai chữ 'b').

Chúng ta có thể duyệt qua tất cả các "trung tâm" có thể có trong chuỗi. Đối với mỗi trung tâm, chúng ta mở rộng ra hai bên (sang trái và sang phải) để tìm Palindrome dài nhất có trung tâm đó. Trung tâm có thể là từng ký tự (index i, tương ứng với việc bắt đầu mở rộng từ left = i, right = i) hoặc khoảng trống giữa hai ký tự (tương ứng với việc bắt đầu mở rộng từ left = i, right = i + 1).

Chúng ta sẽ sử dụng một hàm trợ giúp expandAroundCenter nhận chuỗi và hai chỉ số left, right ban đầu, sau đó mở rộng ra hai bên chừng nào các ký tự còn khớp và nằm trong phạm vi chuỗi. Hàm này sẽ trả về độ dài của Palindrome tìm được.

#include <iostream>
#include <string>
#include <algorithm> // Để sử dụng std::max

// Hàm trợ giúp để mở rộng quanh trung tâm và trả về độ dài Palindrome
int expandAroundCenter(const std::string& s, int left, int right) {
    // Mở rộng chừng nào còn trong phạm vi chuỗi và ký tự khớp nhau
    while (left >= 0 && right < s.length() && s[left] == s[right]) {
        left--;
        right++;
    }
    // Độ dài của Palindrome là (right - 1) - (left + 1) + 1 = right - left - 1
    return right - left - 1;
}

std::string longestPalindromeSubstring(const std::string& s) {
    if (s.empty()) {
        return "";
    }
    if (s.length() == 1) {
        return s;
    }

    int start = 0; // Chỉ số bắt đầu của Palindrome dài nhất tìm được
    int maxLen = 0; // Độ dài của Palindrome dài nhất tìm được

    // Duyệt qua tất cả các ký tự trong chuỗi
    for (int i = 0; i < s.length(); ++i) {
        // Trường hợp 1: Palindrome có độ dài lẻ (trung tâm là ký tự i)
        int len1 = expandAroundCenter(s, i, i);

        // Trường hợp 2: Palindrome có độ dài chẵn (trung tâm giữa i và i+1)
        int len2 = expandAroundCenter(s, i, i + 1);

        // Lấy độ dài lớn nhất giữa hai trường hợp
        int currentLen = std::max(len1, len2);

        // Nếu tìm thấy Palindrome dài hơn Palindrome dài nhất hiện tại
        if (currentLen > maxLen) {
            maxLen = currentLen;
            // Tính toán chỉ số bắt đầu của Palindrome mới tìm được
            // Đối với len1 (lẻ): start = i - (len1 - 1) / 2
            // Đối với len2 (chẵn): start = i - (len2 / 2 - 1)
            // Cả hai có thể được tổng quát thành: start = i - (currentLen - 1) / 2
            start = i - (currentLen - 1) / 2;
        }
    }

    // Trích xuất chuỗi con Palindrome dài nhất
    return s.substr(start, maxLen);
}

int main() {
    std::string str1 = "babad"; // Expected: "bab" or "aba"
    std::string str2 = "cbbd";  // Expected: "bb"
    std::string str3 = "a";     // Expected: "a"
    std::string str4 = "ac";    // Expected: "a" (hoặc "c")
    std::string str5 = "forgeeksskeegfor"; // Expected: "geeksskeeg"

    std::cout << "Longest palindrome substring of \"" << str1 << "\" is: " << longestPalindromeSubstring(str1) << std::endl;
    std::cout << "Longest palindrome substring of \"" << str2 << "\" is: " << longestPalindromeSubstring(str2) << std::endl;
    std::cout << "Longest palindrome substring of \"" << str3 << "\" is: " << longestPalindromeSubstring(str3) << std::endl;
    std::cout << "Longest palindrome substring of \"" << str4 << "\" is: " << longestPalindromeSubstring(str4) << std::endl;
    std::cout << "Longest palindrome substring of \"" << str5 << "\" is: " << longestPalindromeSubstring(str5) << std::endl;

    return 0;
}

Giải thích mã:

• Hàm expandAroundCenter là trung tâm của thuật toán. Nó nhận left và right làm điểm bắt đầu (có thể cùng một điểm hoặc hai điểm liền kề) và mở rộng ra ngoài cho đến khi không còn là Palindrome hoặc ra khỏi biên. Nó trả về độ dài của Palindrome tìm được.
• Hàm longestPalindromeSubstring duyệt qua từng chỉ số i từ 0 đến n-1.
• Đối với mỗi i, nó gọi expandAroundCenter hai lần:
  • (s, i, i): Kiểm tra Palindrome có độ dài lẻ, trung tâm tại i.
  • (s, i, i + 1): Kiểm tra Palindrome có độ dài chẵn, trung tâm giữa i và i+1.
• std::max được sử dụng để lấy độ dài lớn nhất giữa hai trường hợp.
• Nếu currentLen lớn hơn maxLen hiện tại, chúng ta cập nhật maxLen và tính lại start index của Palindrome dài nhất mới. Công thức start = i - (currentLen - 1) / 2 hoạt động cho cả độ dài lẻ và chẵn.
• Sau khi duyệt hết các trung tâm, start và maxLen sẽ lưu trữ thông tin về Palindrome con dài nhất.
• s.substr(start, maxLen) trích xuất và trả về chuỗi con đó.

Độ phức tạp thời gian của thuật toán này là O(N^2) vì có N trung tâm tiềm năng và mỗi lần mở rộng có thể đi hết chuỗi (O(N)). Độ phức tạp không gian là O(1) (nếu không tính bộ nhớ cho chuỗi kết quả).

Tìm Palindrome con dài nhất (Longest Palindromic Subsequence)

Đây là một bài toán khác có tên gọi tương tự nhưng khác biệt quan trọng: tìm Palindrome con (subsequence - các ký tự không nhất thiết phải liên tục) dài nhất.

Ví dụ:

• Trong chuỗi "abca", các subsequence là Palindrome bao gồm "a", "b", "c", "aa". Palindrome subsequence dài nhất là "aca" (độ dài 3).
• Trong chuỗi "bbbab", các Palindrome subsequence bao gồm "b", "bb", "bbb", "bbbb", "bab", "bkb" (nếu có k). Palindrome subsequence dài nhất là "bbbb" (độ dài 4).

Bài toán Longest Palindromic Subsequence (LPS) thường được giải bằng Quy hoạch động. Một tính chất quan trọng là độ dài của Longest Palindromic Subsequence của một chuỗi s bằng với độ dài của Longest Common Subsequence (LCS) giữa s và chuỗi đảo ngược của nó (s').

Ví dụ: LPS("abca") = LCS("abca", "acba"). LCS("abca", "acba") -> "aca" (độ dài 3).

Giải thuật LCS sử dụng bảng DP kích thước N x N, với độ phức tạp thời gian O(N^2) và không gian O(N^2). Việc triển khai chi tiết thuật toán LCS nằm ngoài phạm vi của bài viết này, nhưng hiểu được mối liên hệ giữa LPS và LCS là một điểm quan trọng.

Bài tập ví dụ:

[Xâu kí tự].Ký tự xuất hiện ở cả 2 xâu.

Cho 2 xâu kí tự S1 và S2 không quá 1000 kí tự,hãy in ra các kí tự xuất hiện ở cả 2 xâu theo thứ tự từ điển, chú ý mỗi kí tự chỉ liệt kê một lần. Sau đó tiếp tục liệt kê các kí tự xuất hiện ở 1 trong 2 xâu theo thứ tự từ điển.

Input Format

Dòng đầu tiên là xâu S1. Dòng thứ 2 là xâu S2. Các ký tự trong 2 xâu chỉ bao gồm chữ cái in hoa hoặc in thường.

Constraints

.

Output Format

Dòng 1 in ra các ký tự xuất hiện ở cả 2 xâu theo thứ tự từ điển tăng dần. Dòng 2 in ra các ký tự xuất hiện ở 1 trong 2 xâu theo thứ tự từ điển tăng dần.

Ví dụ:

Dữ liệu vào

mabchrirhgwaq
hvndcnmandnce

Dữ liệu ra

achm
abcdeghimnqrvw

Để giải bài toán này một cách hiệu quả trong C++, bạn có thể làm theo hướng dẫn ngắn gọn sau:

1. Sử dụng mảng boolean hoặc std::set:

   • Cách 1 (Mảng boolean): Dùng hai mảng boolean, ví dụ bool presentS1[256] và bool presentS2[256], khởi tạo tất cả là false. Duyệt qua từng ký tự trong S1, đánh dấu presentS1[ky_tu] = true. Tương tự với S2 và presentS2.
   • Cách 2 (std::set): Dùng hai std::set<char>, một cho S1 (setS1) và một cho S2 (setS2). Duyệt qua từng ký tự trong S1, thêm vào setS1. Tương tự với S2 và setS2.

2. Tìm ký tự xuất hiện ở cả 2 xâu (Giao):

   • Duyệt qua tất cả các ký tự có thể có (ví dụ: từ 'a' đến 'z' và từ 'A' đến 'Z').
   • Nếu sử dụng mảng boolean: Kiểm tra xem ký tự hiện tại c có presentS1[c] và presentS2[c] đều là true không. Nếu có, thêm c vào kết quả cho dòng 1.
   • Nếu sử dụng std::set: Kiểm tra xem ký tự hiện tại c có tồn tại trong cả setS1 và setS2 không (dùng phương thức count). Nếu có, thêm c vào kết quả cho dòng 1.
   • Kết quả này sẽ tự động duy nhất và theo thứ tự từ điển nếu bạn duyệt ký tự theo thứ tự từ điển ('a' đến 'z', rồi 'A' đến 'Z').

3. Tìm ký tự xuất hiện ở 1 trong 2 xâu (Hợp):

   • Tiếp tục duyệt qua tất cả các ký tự có thể có ('a' đến 'z', 'A' đến 'Z').
   • Nếu sử dụng mảng boolean: Kiểm tra xem ký tự hiện tại c có presentS1[c] hoặc presentS2[c] là true không. Nếu có, thêm c vào kết quả cho dòng 2.
   • Nếu sử dụng std::set: Kiểm tra xem ký tự hiện tại c có tồn tại trong setS1 hoặc setS2 không. Nếu có, thêm c vào kết quả cho dòng 2.
   • Kết quả này cũng sẽ tự động duy nhất và theo thứ tự từ điển.

4. In kết quả: In kết quả cho dòng 1, xuống dòng, sau đó in kết quả cho dòng 2.

Lưu ý: Cả hai cách (mảng boolean hoặc std::set) đều hiệu quả. Mảng boolean có thể nhanh hơn một chút do truy cập trực tiếp, trong khi std::set cung cấp tính năng duy nhất và sắp xếp tự động tiện lợi hơn trong một số trường hợp khác, nhưng ở đây ta có thể tự đảm bảo thứ tự bằng cách duyệt các ký tự. Với tập ký tự chỉ là chữ cái, việc duyệt từ 'a' đến 'z' rồi 'A' đến 'Z' là đơn giản nhất để đảm bảo thứ tự từ điển.

Làm thêm nhiều bài tập miễn phí tại đây