Longest Happy Prefix trong C++

Cho chuỗi s, tìm "happy prefix" dài nhất: tiền tố không rỗng cũng là hậu tố (trừ chính chuỗi). Nếu không có, trả về chuỗi rỗng.

Ví dụ: "madam" → tiền tố: "m","ma","mad","mada"; hậu tố: "m","am","dam","adam" → chung dài nhất: "m".

Giải thuật (KMP LPS Array)

Tính mảng LPS (Longest Prefix Suffix) của KMP. LPS[i] = độ dài tiền tố dài nhất của s[0..i] cũng là hậu tố. Kết quả = s.substr(0, LPS[n-1]).

Ví dụ triển khai C++

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

class Solution {
    vector<int> computeLPS(string s) {
        int n = s.size();
        vector<int> lps(n, 0);
        for (int i = 1, len = 0; i < n; ) {
            if (s[i] == s[len]) {
                lps[i++] = ++len;
            } else if (len > 0) {
                len = lps[len - 1];
            } else {
                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;
}

Đầu vào / Đầu ra

Input: "madam"
Output: "m"