Clear c++ solution with KMP next[]


  • 3
    V
    string shortestPalindrome(string s) {
    	string s2 = s;
    	reverse(s2.begin(), s2.end());
    	string ss = s + '#' + s2;
    	int n = ss.size();
    	vector<int> next(n, 0);
    	int k = 0;
    	for (int i = 1; i < n; i++) {
    		while (k > 0 && ss[i] != ss[k])
    			k = next[k - 1];
    		if (ss[i] == ss[k])
    			k++;
    		next[i] = k;
    	}
    	int m = s.size() - next[n - 1];
    	string res = s2.substr(0, m) + s;
    	return res;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.