Palindrome ngắn nhất (Shortest Palindrome) trong C++

Cho chuỗi s, được phép thêm ký tự vào đầu chuỗi. Tìm palindrome ngắn nhất có thể tạo được.

Ví dụ

s = "abcc" → thêm "ccb" vào đầu → "ccbabcc".

Thuật toán: KMP (LPS Array)

Ý tưởng: Tìm tiền tố dài nhất của s cũng là hậu tố của reverse(s) (tức là palindrome bắt đầu từ đầu).

1. s2 = reverse(s).
2. Tạo chuỗi s + "#" + s2 (dấu # tránh trùng lặp).
3. Tính mảng lps (Longest Prefix Suffix) của chuỗi này.
4. lps.back() = độ dài palindrome dài nhất bắt đầu từ đầu.
5. Phần còn lại của s (từ lps.back() đến cuối) đảo ngược thêm vào đầu.

Cài đặt C++

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

class Solution {
public:
    string shortestPalindrome(string s) {
        int n = s.size();
        string rev = s;
        reverse(rev.begin(), rev.end());
        string combined = s + "#" + rev;
        vector<int> lps(combined.size(), 0);
        for (int i = 1, j = 0; i < combined.size(); ) {
            if (combined[i] == combined[j]) {
                lps[i++] = ++j;
            } else if (j > 0) {
                j = lps[j-1];
            } else {
                i++;
            }
        }
        string extra = s.substr(lps.back());
        reverse(extra.begin(), extra.end());
        return extra + s;
    }
};

int main() {
    Solution ob;
    cout << ob.shortestPalindrome("abcc");
    return 0;
}

Độ phức tạp

• Thời gian: O(n) — KMP linear.
• Không gian: O(n) — mảng LPS.

Input / Output

Input:  "abcc"
Output: ccbabcc