题解：P6080 [USACO05DEC] Cow Patterns G

KMP？树状数组？去你的。

所有的字符串题都可以用哈希解的哦～
——阿毛

为了光辉阿毛遗德（咕噜咕噜），我们决定用哈希来轻松搞定这个题喵～！

首先，我们要思考一下，如何用哈希来描述这个匹配问题呢？其实很简单哦喵！只要我们保持相对的大小关系一致，那么就是匹配啦喵～所以呢，我们可以把每个数换成自己的排名，嗯，简单来说就是离散化咯～然后用哈希来处理就好了喵～

举个例子吧，题面中的

\left[2,10,10,7,3,2\right]

，我们可以把它转化成

\left[1,4,4,3,2,1\right]

，这个很简单喵。(｡•̀ᴗ•́｡)

然后嘛，哈希值就可以计算出来啦～每个位置的值就可以通过这种方式转换成排名喵～（咕噜咕噜，狐狸耳朵都在抖啦）

现在要考虑的是母串上的区间怎么移动？这个问题怎么处理喵？(・o・)

其实很简单哟～区间会随着每一步的移动而变化，所以排名也会随之变化。要怎么保持哈希的更新喵？

我们可以为每一个值开一个哈希数组，记作

h

。这样每个数组

h_x

就是计算一个只有

x

出现的串喵～计算方式和普通的哈希类似，只不过它计算的是：仅当原串上的位置是

x

的时候，才加一喵！这样就不会错过任何一个位置啦～由于值域

S \le 25

，这种方法还是蛮能接受的呢～而且因为区间的长度是固定的，所以这个哈希就可以轻松地滚动更新啦喵～(•̀ᴗ•́)و ̑̑

就比如说，当我们区间是

\left[\color{#CCC}5,6,\color{#33A}2,10,10,7,3,2\color{#CCC},9\color{black}\right]

，像这样一个例子的蓝色部分，哈希数组

h_{10}

维护的就会是

\left[0,1,1,0,0,0\right]

的形式。因为在这两位置上，都是

10

呢！这个哈希值就很好更新啦喵～ (●´ω｀●)

每次我们移动区间的时候呢，只需要整体乘上一个

base

，然后再分别处理新加入的右边元素和左边退出的元素就好啦喵！

然后呢，我们~~事后发现可以用桶，但是阿毛以为~~需要开一个 set，用来记录当前区间内有多少种不同的牛哟～如果我们发现区间的牛的数量和模式串中的一样多，那就可以从小到大地处理出每一个排名对应的真实编号喵～

然后呀，只要把它们每个对应的哈希数组分别乘上它们的排名，求个和，就能得到完整的哈希啦喵！这样，最后我们就可以轻松比较一下哈希值是不是一致了喵～ (づ｡◕‿‿◕｡)づ

到目前为止呢，数据完全不卡阿毛，自然溢出也能处理喵～所以问题就解决啦！好简单对吧喵～(≧▽≦)

你说阿毛语言太花哨难懂了？没关系，还有更丑陋的代码喵～

CPP

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define int long long

using namespace std;
using namespace __gnu_pbds;

const int N = 100005, base = 19260817;

int a[N], t[N];
int h[N];
set<int> st;
gp_hash_table<int, int> mp;

signed main() {
  int n, k, s;
  cin >> n >> k >> s;
  if (k > n) {
    cout << 0;
    return 0;
  }
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= k; i++) {
    cin >> t[i];
    st.insert(t[i]);
  }
  int x = 0;
  for (auto it : st) {
    mp[it] = ++x;
  }
  unsigned int hsh = 0, basep = 1;
  for (int i = 1; i <= k; i++) {
    hsh = (hsh * base + mp[t[i]]);
    basep *= base;
  }
  multiset<int> ms;
  st.clear();
  for (int i = 1; i <= k; i++) {
    if (ms.find(a[i]) == ms.end()) {
      st.insert(a[i]);
    }
    ms.insert(a[i]);
    for (int j = 1; j <= s; j++) {
      h[j] = h[j] * base + (a[i] == j);
    }
  }
  vector<int> ans;
  if (st.size() == x) {
    int y = 0;
    mp.clear();
    for (auto it : st) {
      mp[++y] = it;
    }
    unsigned int hsh2 = 0;
    for (int i = 1; i <= x; i++) {
      hsh2 += h[mp[i]] * i;
    }
    if (hsh2 == hsh) {
      ans.push_back(1);
    }
  }
  for (int i = k + 1; i <= n; i++) {
    ms.erase(ms.find(a[i - k]));
    if (ms.find(a[i - k]) == ms.end()) {
      st.erase(a[i - k]);
    }
    if (ms.find(a[i]) == ms.end()) {
      st.insert(a[i]);
    }
    ms.insert(a[i]);
    for (int j = 1; j <= s; j++) {
      h[j] = h[j] * base + (a[i] == j) - (a[i - k] == j) * basep;
    }
    if (st.size() == x) {
      int y = 0;
      mp.clear();
      for (auto it : st) {
        mp[++y] = it;
      }
      unsigned int hsh2 = 0;
      for (unsigned int i = 1; i <= x; i++) {
        hsh2 += h[mp[i]] * i;
      }
      if (hsh2 == hsh) {
        ans.push_back(i - k + 1);
      }
    }
  }
  cout << ans.size() << '\n';
  for (int i : ans) {
    cout << i << '\n';
  }
}

灵感来源：https://www.luogu.com.cn/article/lnfxpwm6

不可爱的“原文”链接：https://www.luogu.com.cn/paste/aklynhtr

本文为实验性文风，希望得到大家的理解和支持。~~翻译由 DeepSeek R1 完成。~~

题解：P6080 [USACO05DEC] Cow Patterns G

文章操作

相关推荐

评论

题解：P6080 [USACO05DEC] Cow Patterns G