Longest Happy Prefix: คำนำหน้าที่ยาวที่สุดที่เป็นคำท้ายใน C++

ปัญหา

กำหนดสตริง s หา Happy Prefix ที่ยาวที่สุด โดย Happy Prefix คือ Prefix ที่ไม่ว่าง และเป็น Suffix ด้วย (ยกเว้นสตริงทั้งหมด)

ตัวอย่าง: "madam" → Prefixes: "m", "ma", "mad", "mada" Suffixes: "m", "am", "dam", "adam" → ตรงกันที่ "m" → คำตอบ: "m"

แนวคิด: KMP Prefix Function (LPS Array)

LPS (Longest Prefix Suffix) Array: lps[i] = ความยาวของ Proper Prefix ที่เป็น Suffix ของ s[0..i]

การสร้าง LPS Array

i:  0  1  2  3  4
s:  m  a  d  a  m
lps:0  0  0  0  1

lps[n-1] = ความยาว Happy Prefix ที่ยาวที่สุด

อัลกอริทึมสร้าง LPS (O(n))

lps[0] = 0
i = 1, len = 0
while i < n:
    if s[i] == s[len]:
        len++
        lps[i] = len
        i++
    else:
        if len > 0:
            len = lps[len-1]  // fallback
        else:
            lps[i] = 0
            i++

โค้ด C++

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

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

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

ตัวอย่างเพิ่มเติม

ความซับซ้อน

• Time: O(n)
• Space: O(n)

Input / Output

Input:  "madam"
Output: "m"