class Solution {
public:
    vector<int> process_lps(string s) {
        int j = 0, i = 1;
        vector<int> lps((int) s.size(), 0);
        lps[0] = 0;
        while(i < (int) s.size()) {
            if(s[i] == s[j]) {
                lps[i] = j + 1;
                i++;
                j++;
            }
            else {
                if(j != 0) {
                    j = lps[j - 1];
                }
                else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    string longestPrefix(string s) {
        vector<int> v = process_lps(s);

        return s.substr(0, v[(int) v.size() - 1]);
    }
};