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); } };
