题目地址：

https://leetcode.com/problems/number-of-subarrays-that-match-a-pattern-ii/description/

给定一个长$n$数组$a$，和一个只含$-1,0,1$的长$m$数组$p$，题目保证$n\ge 2,m\ge 1$。如果存在$a$的一个长$m+1$的子数组，使得$a[i]<a[i+1],a[i]=a[i+1],a[i]>a[i+1]$分别等价于$p[i]=1,0,-1$，就说这段子数组满足$p$的模式。问$a$有多少个子数组满足$p$模式。

先将$a$做一个变换，变换为$s$数组，使得$s[i]=\mathrm{sgn}(a[i+1]-a[i])$，问题转化为问$s$中含子数组$p$多少次，可以用KMP算法来做。代码如下：

class Solution {
public:
  int countMatchingSubarrays(vector<int> &a, vector<int> &p) {
    int n = a.size(), m = p.size();
    if (n - 1 < m) return 0;
    vector<int> s(n);
    for (int i = 1; i < n; i++)
      s[i] = (a[i] > a[i - 1]) - (a[i] < a[i - 1]);

    p.insert(p.begin(), 0);
    auto ne = [&](auto &p) {
      vector<int> ne(m + 1);
      for (int i = 2, j = 0; i <= m; i++) {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j++;
        ne[i] = j;
      }
      return ne;
    }(p);

    int res = 0;
    for (int i = 1, j = 0; i <= n - 1; i++) {
      while (j && s[i] != p[j + 1]) j = ne[j];
      if (s[i] == p[j + 1]) j++;
      if (j == m) {
        res++;
        j = ne[j];
      }
    }

    return res;
  }
};

时间复杂度$O(n+m)$，空间$O(m)$。