strStr II – Python 3 (Week 13 – 07)

class Solution:
    """
    @param: source: A source string
    @param: target: A target string
    @return: An integer as index
    """
    def strStr2(self, source, target):
        # write your code here
        if source == None or target == None:
            return -1
            
        m, n = len(source), len(target)
        if n == 0:
            return 0
        if m < n:
            return -1
        
        power = 1
        base = 10000000
        hashtarget = 0
        for i in range(n):
            power = (power * 31) % base
            hashtarget = (hashtarget * 31 + ord(target[i])) % base
 

        hashcode = 0
        for i in range(m):
            hashcode = (hashcode * 31 + ord(source[i])) % base
            if i < n - 1:
                continue
            if i >= n:
                hashcode = hashcode - (ord(source[i - n]) * power) % base
                if hashcode < 0:
                    hashcode += base
            
            if hashcode == hashtarget and source[i - n + 1: i + 1] == target:
                return i - n + 1
        
        return -1