<s> """<STR_LIT>""" <EOL> __author__ = '<STR_LIT>' <EOL> class Solution : <EOL> def strStr_brute_force ( self , haystack , needle ) : <EOL> """<STR_LIT>""" <EOL> l_hay = len ( haystack ) <EOL> l_ndl = len ( needle ) <EOL> for i in xrange ( l_hay - l_ndl + <NUM_LIT:1> ) : <EOL> if haystack [ i : i + l_ndl ] == needle : <EOL> return haystack [ i : ] <EOL> return None <EOL> def strStr ( self , haystack , needle ) : <EOL> """<STR_LIT>""" <EOL> ln = len ( needle ) <EOL> lh = len ( haystack ) <EOL> if ln == <NUM_LIT:0> : <EOL> return haystack <EOL> if ln == <NUM_LIT:1> : <EOL> try : <EOL> index = haystack . index ( needle ) <EOL> return haystack [ index : ] <EOL> except ValueError : <EOL> return None <EOL> T = [ <NUM_LIT:0> for _ in xrange ( ln ) ] <EOL> T [ <NUM_LIT:0> ] = - <NUM_LIT:1> <EOL> T [ <NUM_LIT:1> ] = <NUM_LIT:0> <EOL> pos = <NUM_LIT:2> <EOL> cnd = <NUM_LIT:0> <EOL> while pos < ln : <EOL> if needle [ pos - <NUM_LIT:1> ] == needle [ cnd ] : <EOL> cnd += <NUM_LIT:1> <EOL> T [ pos ] = cnd <EOL> pos += <NUM_LIT:1> <EOL> elif T [ cnd ] != - <NUM_LIT:1> : <EOL> cnd = T [ cnd ] <EOL> else : <EOL> cnd = <NUM_LIT:0> <EOL> T [ pos ] = cnd <EOL> pos += <NUM_LIT:1> <EOL> i = <NUM_LIT:0> <EOL> m = <NUM_LIT:0> <EOL> while m + i < lh : <EOL> if needle [ i ] == haystack [ m + i ] : <EOL> i += <NUM_LIT:1> <EOL> if i == ln : <EOL> return haystack [ m : ] <EOL> else : <EOL> if T [ i ] != - <NUM_LIT:1> : <EOL> m = m + i - T [ i ] <EOL> i = T [ i ] <EOL> else : <EOL> m += <NUM_LIT:1> <EOL> i = <NUM_LIT:0> <EOL> return None <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> needle = "<STR_LIT>" <EOL> haystack = "<STR_LIT>" <EOL> needle = "<STR_LIT>" <EOL> haystack = "<STR_LIT>" <EOL> solution = Solution ( ) <EOL> assert solution . strStr_brute_force ( haystack , needle ) == solution . strStr ( haystack , needle ) </s>
