Description

Submission

class Solution {
public:
    string longestPrefix(string s) {
        // dp[i] = k: the maximum k s.t. dp[0:k-1] == dp[i-k+1, i]
        int n = s.size();
        vector<int> dp(n, 0);

        for(int i = 1; i < n; ++i) {
            int j = dp[i-1]; // j is k
            while(j >= 1 && s[j] != s[i]) {
                j = dp[j-1];
            }
            dp[i] = j + (s[i] == s[j]);
        }
        int len = dp[n-1];
        return s.substr(0, len);
    }
};