Chương trình C++ tách 2 chuỗi để tạo palindrome

Chuỗi palindrome: đọc xuôi và ngược giống nhau.

Cho 2 chuỗi 'a' và 'b' cùng độ dài. Tách tại chỉ số nào đó, kiểm tra xem ghép prefix của a + suffix của b HOẶC suffix của a + prefix của b có tạo thành palindrome không.

Ví dụ

Input 1: a = "abcdef", b = "fedcba"

Output: True

Tách tại index 2: "abc|def" và "fed|cba" → "abc" + "cba" = palindrome.

Input 2: a = "eatable", b = "tableau"

Output: False

Cách tiếp cận: Two-pointer

• Khởi tạo 2 con trỏ low=0, high=length-1
• Nếu độ dài < 2 → True
• Duyệt chuỗi, so sánh ký tự từ 2 đầu
• Hàm checkPalindromic(a, b) gọi Split(a, b) || Split(b, a)
• Split() kiểm tra palindrome sau khi tách

Code C++

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

bool isPalindrome(string a, int low, int high) {
    while (low < high) {
        if (a[low] != a[high]) return false;
        low++; high--;
    }
    return true;
}

bool Split(string a, string b) {
    int low = 0, high = b.size() - 1;
    while (low < high && a[low] == b[high]) { low++; high--; }
    return isPalindrome(a, low, high) || isPalindrome(b, low, high);
}

bool checkPalindromic(string a, string b) {
    if (a.size() < 2) return true;
    return Split(a, b) || Split(b, a);
}

int main() {
    string a = "abcpqr", b = "mnocba";
    if (checkPalindromic(a, b)) cout << "True" << endl;
    else cout << "False" << endl;
    return 0;
}

Kết quả

True

Tách tại index 2: "abc" + "cba" = palindrome.