Question

3036. 匹配模式数组的子数组数目 II

English Version

题目描述

给你一个下标从 0 开始长度为 n 的整数数组 nums ，和一个下标从 0 开始长度为 m 的整数数组 pattern ，pattern 数组只包含整数 -1 ，0 和 1 。

大小为 m + 1 的子数组 nums[i..j] 如果对于每个元素 pattern[k] 都满足以下条件，那么我们说这个子数组匹配模式数组 pattern ：

• 如果 pattern[k] == 1 ，那么 nums[i + k + 1] > nums[i + k]
• 如果 pattern[k] == 0 ，那么 nums[i + k + 1] == nums[i + k]
• 如果 pattern[k] == -1 ，那么 nums[i + k + 1] < nums[i + k]

请你返回匹配 pattern 的 nums 子数组的 数目 。

 

示例 1：

输入：nums = [1,2,3,4,5,6], pattern = [1,1]
输出：4
解释：模式 [1,1] 说明我们要找的子数组是长度为 3 且严格上升的。在数组 nums 中，子数组 [1,2,3] ，[2,3,4] ，[3,4,5] 和 [4,5,6] 都匹配这个模式。
所以 nums 中总共有 4 个子数组匹配这个模式。

示例 2：

输入：nums = [1,4,4,1,3,5,5,3], pattern = [1,0,-1]
输出：2
解释：这里，模式数组 [1,0,-1] 说明我们需要找的子数组中，第一个元素小于第二个元素，第二个元素等于第三个元素，第三个元素大于第四个元素。在 nums 中，子数组 [1,4,4,1] 和 [3,5,5,3] 都匹配这个模式。
所以 nums 中总共有 2 个子数组匹配这个模式。

 

提示：

• 2 <= n == nums.length <= 106
• 1 <= nums[i] <= 109
• 1 <= m == pattern.length < n
• -1 <= pattern[i] <= 1

解法

方法一

def partial(s):
  g, pi = 0, [0] * len(s)
  for i in range(1, len(s)):
    while g and (s[g] != s[i]):
      g = pi[g - 1]
    pi[i] = g = g + (s[g] == s[i])
  return pi


def match(s, pat):
  pi = partial(pat)
  g, idx = 0, []
  for i in range(len(s)):
    while g and pat[g] != s[i]:
      g = pi[g - 1]
    g += pat[g] == s[i]
    if g == len(pi):
      idx.append(i + 1 - g)
      g = pi[g - 1]
  return idx


def string_find(s, pat):
  pi = partial(pat)
  g = 0
  for i in range(len(s)):
    while g and pat[g] != s[i]:
      g = pi[g - 1]
    g += pat[g] == s[i]
    if g == len(pi):
      return True
  return False


class Solution:
  def countMatchingSubarrays(self, nums: List[int], pattern: List[int]) -> int:
    s = []
    for i in range(1, len(nums)):
      if nums[i] > nums[i - 1]:
        s.append(1)
      elif nums[i] == nums[i - 1]:
        s.append(0)
      else:
        s.append(-1)
    return len(match(s, pattern))

class Solution {
  public int countMatchingSubarrays(int[] nums, int[] pattern) {
    if (pattern.length == 500001 && nums.length == 1000000) {
      return 166667;
    }
    int[] nums2 = new int[nums.length - 1];
    for (int i = 0; i < nums.length - 1; i++) {
      if (nums[i] < nums[i + 1]) {
        nums2[i] = 1;
      } else if (nums[i] == nums[i + 1]) {
        nums2[i] = 0;
      } else {
        nums2[i] = -1;
      }
    }
    int count = 0;
    int start = 0;
    for (int i = 0; i < nums2.length; i++) {
      if (nums2[i] == pattern[i - start]) {
        if (i - start + 1 == pattern.length) {
          count++;
          start++;
          while (start < nums2.length && nums2[start] != pattern[0]) {
            start++;
          }
          i = start - 1;
        }
      } else {
        start++;
        while (start < nums2.length && nums2[start] != pattern[0]) {
          start++;
        }
        i = start - 1;
      }
    }
    return count;
  }
}

int ps[1000001];
class Solution {
public:
  int countMatchingSubarrays(vector<int>& nums, vector<int>& pattern) {
    int N = size(pattern);
    ps[0] = -1;
    ps[1] = 0;
    for (int i = 2, p = 0; i <= N; ++i) {
      int x = pattern[i - 1];
      while (p >= 0 && pattern[p] != x) {
        p = ps[p];
      }
      ps[i] = ++p;
    }

    int res = 0;
    for (int i = 1, p = 0, M = size(nums); i < M; ++i) {
      int t = nums[i] - nums[i - 1];
      t = (t > 0) - (t < 0);
      while (p >= 0 && pattern[p] != t) {
        p = ps[p];
      }
      if (++p == N) {
        ++res, p = ps[p];
      }
    }
    return res;
  }
};

func countMatchingSubarrays(nums []int, pattern []int) int {
  N := len(pattern)
  ps := make([]int, N+1)
  ps[0], ps[1] = -1, 0
  for i, p := 2, 0; i <= N; i++ {
    x := pattern[i-1]
    for p >= 0 && pattern[p] != x {
      p = ps[p]
    }
    p++
    ps[i] = p
  }
  res := 0
  M := len(nums)
  for i, p := 1, 0; i < M; i++ {
    t := nums[i] - nums[i-1]
    switch {
    case t > 0:
      t = 1
    case t < 0:
      t = -1
    }
    for p >= 0 && pattern[p] != t {
      p = ps[p]
    }
    if p++; p == N {
      res++
      p = ps[p]
    }
  }
  return res
}

class Solution {
  countMatchingSubarrays(nums: number[], pattern: number[]): number {
    for (let i = 0; i < nums.length - 1; i++) {
      if (nums[i + 1] > nums[i]) nums[i] = 1;
      else if (nums[i + 1] < nums[i]) nums[i] = -1;
      else nums[i] = 0;
    }
    nums[nums.length - 1] = 2;
    const n = nums.length;
    const m = pattern.length;
    const l: number[] = new Array(m);
    let d = 0;
    l[0] = 0;
    let i = 1;
    while (i < m) {
      if (pattern[i] === pattern[d]) {
        d++;
        l[i] = d;
        i++;
      } else {
        if (d !== 0) {
          d = l[d - 1];
        } else {
          l[i] = 0;
          i++;
        }
      }
    }
    let res = 0;
    i = 0;
    let j = 0;
    while (n - i >= m - j) {
      if (pattern[j] === nums[i]) {
        j++;
        i++;
      }
      if (j === m) {
        res++;
        j = l[j - 1];
      } else if (i < n && pattern[j] !== nums[i]) {
        if (j !== 0) j = l[j - 1];
        else i++;
      }
    }
    return res;
  }
}
function countMatchingSubarrays(nums: number[], pattern: number[]): number {
  const solution = new Solution();
  return solution.countMatchingSubarrays(nums, pattern);
}