พาลินโดรมสั้นที่สุดใน C++ (Shortest Palindrome)

ภาพรวมปัญหา

เพิ่มตัวอักษรด้านหน้าสตริง ให้กลายเป็นพาลินโดรมที่สั้นที่สุด

ตัวอย่าง

"abcc" → "ccbabcc"

วิธีแก้ปัญหา: KMP (LPS Array)

1. สร้าง s2 = reverse(s)
2. สร้าง pattern = s + "#" + s2
3. คำนวณ LPS (Longest Prefix Suffix) array ของ pattern
4. LPS สุดท้าย = ความยาว prefix ของ s ที่เป็น suffix ของ s2 = พาลินโดรมยาวที่สุดจากต้น
5. นำส่วนที่เหลือของ s2 มาต่อหน้า s

โค้ด C++

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

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

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

ผลลัพธ์

ccbabcc

การวิเคราะห์ความซับซ้อน

• เวลา: O(n)
• พื้นที่: O(n)