<p>You are given a <strong>0-indexed</strong> integer array <code>nums</code> of size <code>n</code>, and a <strong>0-indexed</strong> integer array <code>pattern</code> of size <code>m</code> consisting of integers <code>-1</code>, <code>0</code>, and <code>1</code>.</p>

<p>A <span data-keyword="subarray">subarray</span> <code>nums[i..j]</code> of size <code>m + 1</code> is said to match the <code>pattern</code> if the following conditions hold for each element <code>pattern[k]</code>:</p>

<ul>
	<li><code>nums[i + k + 1] &gt; nums[i + k]</code> if <code>pattern[k] == 1</code>.</li>
	<li><code>nums[i + k + 1] == nums[i + k]</code> if <code>pattern[k] == 0</code>.</li>
	<li><code>nums[i + k + 1] &lt; nums[i + k]</code> if <code>pattern[k] == -1</code>.</li>
</ul>

<p>Return <em>the<strong> count</strong> of subarrays in</em> <code>nums</code> <em>that match the</em> <code>pattern</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4,5,6], pattern = [1,1]
<strong>Output:</strong> 4
<strong>Explanation:</strong> The pattern [1,1] indicates that we are looking for strictly increasing subarrays of size 3. In the array nums, the subarrays [1,2,3], [2,3,4], [3,4,5], and [4,5,6] match this pattern.
Hence, there are 4 subarrays in nums that match the pattern.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,4,4,1,3,5,5,3], pattern = [1,0,-1]
<strong>Output:</strong> 2
<strong>Explanation: </strong>Here, the pattern [1,0,-1] indicates that we are looking for a sequence where the first number is smaller than the second, the second is equal to the third, and the third is greater than the fourth. In the array nums, the subarrays [1,4,4,1], and [3,5,5,3] match this pattern.
Hence, there are 2 subarrays in nums that match the pattern.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= n == nums.length &lt;= 10<sup>6</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= m == pattern.length &lt; n</code></li>
	<li><code>-1 &lt;= pattern[i] &lt;= 1</code></li>
</ul>

import numpy as np

class Solution:
    ## Using the Z-function algorithm.
    ## O(N+M) for both time and space.
    def countMatchingSubarrays(self, nums: List[int], pattern: List[int]) -> int:
        # Transform input into deltas
        nums2: List[int] = [np.sign(nums[x+1]-nums[x]).item() for x in range(len(nums)-1)]

        # Concatenate pattern and nums with a dummy character in between
        concat: List[int] = pattern + ['$'] + nums2
        print(f"{concat=}")

        # Build the Z-function array
        zArray: List[int] = self.buildZArray(concat)
        print(f"{zArray=}")

        # Now check how many values equals to the size of pattern+1 we encounter
        count = 0
        size = len(pattern)
        for z in zArray:
            if z >= size:
                count = count + 1

        return count

    # Here we want to build the Z-array based on the concatenated input parameter.
    def buildZArray(self, concat: List[int]) -> List[int]:
        size = len(concat)
        Z: List[int] = [0] * size
        left = 0
        right = 0

        i = 1
        while i < size:
            # Case where there is nothing, need to compute.
            # This is essentially the start of pattern matching.
            if i > right:
                left = i
                right = i
                while right < size and concat[right-left] == concat[right]:
                    right = right + 1
                Z[i] = right - left
                right = right - 1
            else:
                # We are inside of a z-box
                idx = i - left

                if Z[idx] < right - i + 1:
                    Z[i] = Z[idx]
                else:

                    #print(f"Before resize: {i=}. {idx=}. {left=}. {right=}. {Z=}")

                    # The value Z[idx] is touching/crossing the box
                    # We need to look further. Also resize the box
                    left = i
                    while right < size and concat[right] == concat[right-left]:
                        right = right + 1

                    # Box was resized, now update value in the current Z
                    Z[i] = right - left
                    right = right - 1

                    #print(f"After resize: {i=}. {idx=}. {left=}. {right=}. {Z=}")

            i = i + 1

        return Z

110800