Leecode 28. Implement strStr()

https://leetcode.com/problems/implement-strstr/

One line slick version:
return haystack.find(needle)
Run Time: 48 ms

Other solutions include KMP and rolling hash. Here only rolling hash is presented.

Solution:

# T:O(m + n) S:O(1)
class Solution:
    # @param {string} haystack
    # @param {string} needle
    # @return {integer}
    def strStr(self, haystack, needle):
        N, H = len(needle), len(haystack)
        if N == 0:
            return 0
        if H < N or H == 0:
            return -1
        rolling = lambda x,y: x*29 +y
        getHash = lambda ch: ord(ch) - ord('a')
        nhash = reduce(rolling, map(getHash, needle))
        hhash = reduce(rolling, map(getHash, haystack[:N]))
        if nhash == hhash:
            return 0
        Base = 29**(N-1)
        for i in xrange(N, H):
            hhash -= getHash(haystack[i - N])*Base
            hhash = rolling(hhash, getHash(haystack[i]))
            if nhash == hhash:
                return i - N + 1
        return -1

Run Time: 92 ms