UCloud 的安全秘钥（哈希表计蒜之道第五场）

每个 UCloud 用户会构造一个由数字序列组成的秘钥，用于对服务器进行各种操作。作为一家安全可信的云计算平台，秘钥的安全性至关重要。因此，UCloud 每年会对用户的秘钥进行安全性评估，具体的评估方法如下：

首先，定义两个由数字序列组成的秘钥 $和近似匹配（）的关系。和近似匹配当且仅当同时满足以下两个条件：$

$，即串和串长度相等。$
对于每种数字 $，在中出现的次数等于在中出现的次数。$

此时，我们就称 $和近似匹配，即。例如，。$

UCloud 每年会收集若干不安全秘钥，这些秘钥组成了不安全秘钥集合 $。对于一个秘钥和集合中的秘钥来说，它们的相似值定义为：的所有连续子串中与近似匹配的个数。相似值越高，说明秘钥越不安全。对于不安全秘钥集合中的每个秘钥，你需要输出它和秘钥的相似值，用来对用户秘钥的安全性进行分析。$

输入格式

第一行包含一个正整数 $，表示串的长度。$

第二行包含 $个正整数，表示串。$

接下来一行包含一个正整数 $，表示询问的个数。$

接下来 $个部分：$

每个部分第一行包含一个正整数 $k(1≤k≤n)k(1\leq k\leq n)$

每个部分第二行包含 $个正整数，表示中的一个串。$

输入数据保证 $中所有串长度之和不超过。$

对于简单版本： $1≤n,m≤1001\leq n,m\leq 100$

对于中等版本： $1≤n≤50000,1≤m≤a5001\leq n\leq 50000,1\leq m\leq 500$

对于困难版本： $\le n \le 50000, 1 \le m \le 100000$

输出格式

输出 $行，每行一个整数，即与中每个串近似匹配的的子串数量。$

样例解释

对于第一个询问， $(3,2,1,3)≈(2,3,1,3)(3,2,1,3)\approx(2,3,1,3)$

对于第二个询问， $(1,3)≈(3,1)(1,3)\approx(3,1)$

对于第三个询问， $(3,2)≈(2,3)(3,2)\approx(2,3)$

样例输入

样例输出

2
2
2

题解：

简单

对于一个长度为 $的询问，枚举的一个长度为的子串，然后暴力检验两个集合是否相同即可。$

时间复杂度 $O(n^2m)$

中等

考虑如何优化检验的复杂度，等价于判断两个可重集是否相同，给每个元素一个随机的 $位无符号整数权值，然后全部加起来作为集合的 Hash 值。那么一个子串的 Hash 值可以简单地由前缀和作差得到，每次检验的复杂度为。$

对于一个长度为 $的询问，枚举的一个长度为的子串，然后检验两个集合是否相同即可。$

时间复杂度 $。$

困难

考虑将询问按询问串长分组，那么最多只有 $O(\sqrt{len})$

对于每种长度 $，将的所有长度为的子串的 Hash 值算出，与询问串 Hash 值一起排序，那么询问可以通过双指针实现。$

时间复杂度 $O(n\sqrt{len}\log n)$

//简单版
#include <stdio.h>  
#include <bits/stdc++.h> 
using namespace std;

int s[50000+5],t[50005];;
int vis[50000+5],show[50000+5];  	
set<int>seta;
int n;	
int m;

int main(){
	while(~scanf("%d",&n)){
		for(int i=1;i<=n;i++)scanf("%d",&s[i]);
		scanf("%d",&m);
		while(m--){
			seta.clear();
	        int k;  
	        scanf("%d",&k);  
	        int cnt=0,ans=0;
	        for(int i=1;i<=k;i++){  
	            scanf("%d",&t[i]);   
	            if(vis[t[i]]==0){  
	               seta.insert(t[i]);  
	            }  
	            vis[t[i]]++;  
	            show[t[i]]++;
	        }  
	        int kind=seta.size();
	        cout<<kind<<endl;
	        for(int i=1;i<=k;i++){
	            if(show[s[i]]){  
	                vis[s[i]]--;  
	                if(vis[s[i]]==0) cnt++;  
	                if(vis[s[i]]==-1) cnt--;  
	            }  
	        }  
	        if(cnt==kind) ans++;  
	        for(int i=k+1;i<=n;i++){ 
	            if(show[s[i]]){  
	                vis[s[i]]--;  
	                if(vis[s[i]]==0) cnt++;  
	                if(vis[s[i]]==-1) cnt--;  
	            }  
	            if(show[s[i-k]]){  
	                vis[s[i-k]]++;  
	                if(vis[s[i-k]]==0) cnt++;  
	                if(vis[s[i-k]]==1) cnt--;  
	            }   
	            if(cnt==kind) ans++;  
	        }  
	          
	        memset(vis,0,sizeof(vis));  
	        memset(show,0,sizeof(show));
			printf("%d\n",ans);
		}	
	}
	return 0;
}




//中等版
#include <stdio.h>  
#include <bits/stdc++.h>  
#define mod 1000000007  
typedef long long ll;  
using namespace std;  
int n,m;  
int s[50005],p[50005];  
int flag[50005],vis[50005];  
int main()  
{  
    cin>>n;  
    for(int i=1;i<=n;i++)  
        cin>>s[i];  
    cin>>m;  
    while(m--){  
        int k;  
        cin>>k;  
        int sum=0,ss=0;  
        int ans=0;  
        for(int i=1;i<=k;i++){  
            scanf("%d",p+i);  
            flag[p[i]]=1;  
            if(vis[p[i]]==0){  
                sum++;  
            }  
            vis[p[i]]++;  
        }  
        for(int i=1;i<=k;i++){  
            if(flag[s[i]]==1){  
                vis[s[i]]--;  
                if(vis[s[i]]==0) ss++;  
                if(vis[s[i]]==-1) ss--;  
            }  
        }  
        if(ss==sum) ans++;  
    //  cout<<ss<<endl;  
        for(int i=k+1;i<=n;i++){  
            if(flag[s[i]]==1){  
                vis[s[i]]--;  
                if(vis[s[i]]==0) ss++;  
                if(vis[s[i]]==-1) ss--;  
            }  
            if(flag[s[i-k]]==1){  
                vis[s[i-k]]++;  
                if(vis[s[i-k]]==0) ss++;  
                if(vis[s[i-k]]==1) ss--;  
            }  
    //      cout<<ss<<endl;  
            if(ss==sum) ans++;  
        }  
          
        memset(flag,0,sizeof(flag));  
        memset(vis,0,sizeof(vis));  
        cout<<ans<<endl;  
    }  
    return 0;  
}  


//高级版  不会

UCloud 的安全秘钥（哈希表 计蒜之道第五场）