LC-3036 Hard LeetCode

3036. Number of Subarrays That Match a Pattern II

Array Rolling Hash String Matching Hash Function

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 32% Topics: Array, Rolling Hash, String Matching, Hash Function

Reading material

Arrays & Hashing 12 min String Matching & Hashing 13 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(m)

# kmp
class Solution(object):
    def countMatchingSubarrays(self, nums, pattern):
        """
        :type nums: List[int]
        :type pattern: List[int]
        :rtype: int
        """
        def getPrefix(pattern):
            prefix = [-1]*len(pattern)
            j = -1
            for i in xrange(1, len(pattern)):
                while j+1 > 0 and pattern[j+1] != pattern[i]:
                    j = prefix[j]
                if pattern[j+1] == pattern[i]:
                    j += 1
                prefix[i] = j
            return prefix

        def KMP(text, pattern):
            prefix = getPrefix(pattern)
            j = -1
            for i, x in enumerate(text):
                while j+1 > 0 and pattern[j+1] != x:
                    j = prefix[j]
                if pattern[j+1] == x:
                    j += 1
                if j+1 == len(pattern):
                    yield i-j
                    j = prefix[j]

        return sum(1 for _ in KMP((cmp(nums[i+1], nums[i]) for i in xrange(len(nums)-1)), pattern))

Solution from kamyu104/LeetCode-Solutions · MIT