rk.py

class Solution:
    # 0<= value <= 100  
    base = 101
    # leetcode popular prime number
    p = 10 ** 9 + 7
    
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        l = 0
        r = min(len(nums1), len(nums2))
        
        while l < r:
            mid = (l+r) // 2
            if self.compare(nums1, nums2, mid):
                l = mid + 1
            else:
                r = mid
        
        return l if self.compare(nums1, nums2, l) else l - 1
    
    def compare(self, num1, num2, size):
        _set = self.generateRollingHashSet(num1, size)
        start = num2[:size]
        
        h = self.toRollingHash(num2, size)
        if h in _set and _set[h][0] == start:
            return True
        
        left = self.base ** (size - 1)
        for i in range(size, len(num2)):
            h = h - num2[i-size] * left
            h = h*self.base + num2[i]
            h = h % self.p
            
            # prevent hash collision 
            # check the value again
            if h in _set and _set[h][0] == num2[i-size+1:i+1]:
                return True
            
        return False
        
        
    def toRollingHash(self, num, size):
        h = 0
        for i in range(0, size):
            h = h * self.base + num[i]
            h = h % self.p
        return h
    
    def generateRollingHashSet(self, num, size):
        start = num[:size]
        hash_set = collections.defaultdict(list)
        h = self.toRollingHash(num, size)
        left = self.base ** (size - 1)
        
        hash_set[h].append(start)
        
        for i in range(size, len(num)):
            # abc -> bc -> bcd
            h = h - (num[i-size] * left)
            h = h*self.base + num[i]
            h = h % self.p
            hash_set[h].append(num[i-size+1:i+1])
            
        return hash_set