1392

class Solution {
public:
    vector<int> lps;
    void kmpPreprocess(string pat){
        int n=pat.size(), i=0, j=-1;
        lps.resize(n+1, 0);
        lps[0] = -1;
        while(i<n){
            while(j>=0 && pat[i] != pat[j])
                j = lps[j];
            i++; j++;
            lps[i] = j;
        }
    }

    string longestPrefix(string s) {
        kmpPreprocess(s);
        return s.substr(0, lps.back());
    }
};