c++ solution using z value


  • 0
    G

    Use z value to find the longest palindromic prefix
    O(n) time, O(n) space

    tutorial on z algorithm: http://codeforces.com/blog/entry/3107

    class Solution {
    public:
        string shortestPalindrome(string s) {
            #define ALL(x) x.begin(), x.end()
            if( s.empty() ) return s;
            string t( 2 * s.size(), ' ' );
            copy( ALL(s), t.begin() );
            copy( ALL(s), t.rbegin() );
            vector<int> z( t.size() );
            int L = 0, R = 0;
            for(int i = 1 ; i < z.size() ; ++i) {
    	    if( i > R ) {
    	        for(L = R = i ; R < t.size() && t[R - L] == t[R] ; ++R);
    	        z[i] = R - L, --R;
    	    } else {
    	        if( z[i - L] < R - i + 1 )
        	        z[i] = z[i - L];
    	        else {
    	            for(L = i ; R < t.size() && t[R - L] == t[R] ; ++R);
    	            z[i] = R - L, --R;
    	        }
    	    }
    	}
    	int m = s.size();
    	for(int i = s.size() ; m < t.size() ; --i, ++m)
    	if( z[m] == i ) break;
    	return t.substr( s.size(), m - s.size() ) + s;
        }
    };
    

Log in to reply
 

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