map+hash+双指针 80pts
查看原帖
map+hash+双指针 80pts
761137
Double_Light楼主2023/10/4 15:21

WA on #9,#10

#include<iostream>
#include<map>
#include<string>
#define int long long
using namespace std;
int n,m,x,len,ans1,l=1,r=1,ans2=998244353,cnt;
string s,a[100005];
map<int,int>ma,f;
int Hash(string s){
	x=0;len=s.size();
	for(int i=0;i<len;i++)x*=30,x+=s[i]-'a'+1;
	return x;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s;
		ma[Hash(s)]++;f[Hash(s)]++;
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i];
		if(ma[Hash(a[i])]&&f[Hash(a[i])])ans1++,f[Hash(a[i])]--;
	}
	cout<<ans1<<endl;
	if(ans1==0){
		cout<<0;
		return 0;
	}
	while(l<=m){
		if(ma[Hash(a[l-1])]){
			f[Hash(a[l-1])]--;
			if(!f[Hash(a[l-1])])cnt--;
		}
		while(cnt<ans1&&r<=m){
			int k=Hash(a[r]);
			if(ma[k]){
				if(!f[k])cnt++;
				f[k]++;
			}
			if(cnt==ans1)break;
			r++;
		}
		if(cnt==ans1)ans2=min(ans2,r-l+1);
		l++;
		if(r>m)break;
	}
	cout<<ans2;
	return 0;
}
2023/10/4 15:21
加载中...