<s> class Solution ( object ) : <EOL> def shortestPalindrome ( self , s ) : <EOL> """<STR_LIT>""" <EOL> def getPrefix ( pattern ) : <EOL> prefix = [ - <NUM_LIT:1> ] * len ( pattern ) <EOL> j = - <NUM_LIT:1> <EOL> for i in xrange ( <NUM_LIT:1> , len ( pattern ) ) : <EOL> while j > - <NUM_LIT:1> and pattern [ j + <NUM_LIT:1> ] != pattern [ i ] : <EOL> j = prefix [ j ] <EOL> if pattern [ j + <NUM_LIT:1> ] == pattern [ i ] : <EOL> j += <NUM_LIT:1> <EOL> prefix [ i ] = j <EOL> return prefix <EOL> if not s : <EOL> return s <EOL> A = s + s [ : : - <NUM_LIT:1> ] <EOL> prefix = getPrefix ( A ) <EOL> i = prefix [ - <NUM_LIT:1> ] <EOL> while i >= len ( s ) : <EOL> i = prefix [ i ] <EOL> return s [ i + <NUM_LIT:1> : ] [ : : - <NUM_LIT:1> ] + s <EOL> class Solution2 ( object ) : <EOL> def shortestPalindrome ( self , s ) : <EOL> """<STR_LIT>""" <EOL> def preProcess ( s ) : <EOL> if not s : <EOL> return [ '<STR_LIT>' , '<STR_LIT:$>' ] <EOL> string = [ '<STR_LIT>' ] <EOL> for c in s : <EOL> string += [ '<STR_LIT:#>' , c ] <EOL> string += [ '<STR_LIT:#>' , '<STR_LIT:$>' ] <EOL> return string <EOL> string = preProcess ( s ) <EOL> palindrome = [ <NUM_LIT:0> ] * len ( string ) <EOL> center , right = <NUM_LIT:0> , <NUM_LIT:0> <EOL> for i in xrange ( <NUM_LIT:1> , len ( string ) - <NUM_LIT:1> ) : <EOL> i_mirror = <NUM_LIT:2> * center - i <EOL> if right > i : <EOL> palindrome [ i ] = min ( right - i , palindrome [ i_mirror ] ) <EOL> else : <EOL> palindrome [ i ] = <NUM_LIT:0> <EOL> while string [ i + <NUM_LIT:1> + palindrome [ i ] ] == string [ i - <NUM_LIT:1> - palindrome [ i ] ] : <EOL> palindrome [ i ] += <NUM_LIT:1> <EOL> if i + palindrome [ i ] > right : <EOL> center , right = i , i + palindrome [ i ] <EOL> max_len = <NUM_LIT:0> <EOL> for i in xrange ( <NUM_LIT:1> , len ( string ) - <NUM_LIT:1> ) : <EOL> if i - palindrome [ i ] == <NUM_LIT:1> : <EOL> max_len = palindrome [ i ] <EOL> return s [ len ( s ) - <NUM_LIT:1> : max_len - <NUM_LIT:1> : - <NUM_LIT:1> ] + s </s>
