โปรแกรมหา Prefix ยาวที่สุดที่เป็น Suffix ด้วยใน C++

ให้สตริง s หา prefix ยาวที่สุดที่เป็น suffix เช่นกัน (ไม่นับสตริงทั้งหมด) ถ้าไม่มีคืนสตริงว่าง

ตัวอย่าง: "helloworldhello" → "hello" (prefix "hello" = suffix "hello")

ขั้นตอนการแก้ปัญหา (KMP LPS Array)

1. สร้าง LPS Array (Longest Prefix Suffix) ขนาด n
2. LPS[i] = ความยาว prefix สูงสุดที่เป็น suffix ของ s[0..i]
3. ใช้ two pointers i, j คำนวณแบบ O(N)
4. คำตอบคือ LPS[n-1] ตัวอักษรแรก

ตัวอย่างโค้ด C++

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

class Solution {
public:
    vector<int> lps(string s) {
        int n = s.size();
        vector<int> ret(n);
        int i = 1, j = 0;
        while (i < n) {
            if (s[i] == s[j]) { ret[i] = j+1; i++; j++; }
            else if (j > 0) j = ret[j-1];
            else i++;
        }
        return ret;
    }
    string longestPrefix(string s) {
        int n = s.size();
        if (n == 1) return "";
        vector<int> v = lps(s);
        int x = v[n-1];
        return s.substr(0, x);
    }
};

int main() {
    Solution ob;
    cout << ob.longestPrefix("helloworldhello"); // hello
    return 0;
}

อินพุต

"helloworldhello"

เอาต์พุต

hello