原题大意

对长度为n的数字组成的串，进行m次询问，询问的长度为k，求原串（长度为k）的字串与询问串近似匹配（可以理解成两个集合相同）的个数。

算法分析

对于n<=50000，m <= 100000，以及询问串的总长度不超过200000的数据来说，通过hash给每个元素赋值，然后按长度将询问的字串分组，并且按hash的和排序，可由双指针完成计数。

https://www.jisuanke.com/article/9v3lgyb4

程序代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 200050;
struct E{
    int l;
    int p;
    int v;
    bool friend operator <(E ob1, E ob2){
        return ob1.l == ob2.l ? ob1.v < ob2.v : ob1.l < ob2.l;
    }
}e[maxn];
int w[maxn], f[maxn], a[maxn], ans[maxn];
int x, k, cnt, j, n, m;
void make(int L){
    cnt = 0;
    for(int i = L; i <= n; i++) a[++cnt] = f[i] - f[i-L];
    sort(a+1,a+1+cnt);
    j = k = 1;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) w[i] = w[i-1] * 233 + 17;
    for(int i = 1; i <= n; i++) {
        cin >> x;
        f[i] = f[i-1] + w[x];
    }
    cin >> m;
    for(int i = 1; i <= m; i++){
        cin >> k;
        e[i].l = k;
        e[i].p = i;
        e[i].v = 0;
        while(k--){
            cin >> x;
            e[i].v += w[x];
        }
    }
    sort(e+1,e+1+m);
    for(int i = 1; i <= m; i++){
        if(i == 1 ||e[i].l != e[i-1].l)make(e[i].l);
        while(j<=cnt&&a[j]<=e[i].v)j++;
        while(k<=cnt&&a[k]<e[i].v)k++;
        ans[e[i].p] = j-k;
    }
    for(int i = 1; i <= m; i++)
        cout << ans[i] << endl;
    return 0;
}