蒟蒻求助
查看原帖
蒟蒻求助
376997
Harry27182SDream楼主2021/4/30 18:20

一本通 A 了,可是洛谷只有十分,其他都 WA 了,求大佬帮忙调一下,谢谢~~

#include<bits/stdc++.h>
#define int unsigned long long
#define mod 1000007
using namespace std;
int n,m,ans1,ans2=0x3f3f3f3f,sum,num;
int h1[100005],h2[100005];
char s[100005];
int vis[1000010];
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		int len=strlen(s);
		int p=11;
		for(int j=0;j<len;j++)
		{
			h1[i]*=p;
			h1[i]+=s[j];
			h1[i]%=mod;
		}
	}
	cin>>m; 
	for(int i=1;i<=m;i++)
	{
		cin>>s;
		int len=strlen(s);
		int p=11;
		for(int j=0;j<len;j++)
		{
			h2[i]*=p;
			h2[i]+=s[j];
			h2[i]%=mod;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(h1[i]==h2[j])
			{
				ans1++;
				break;
			}
		}
	}
	int l=1,r=0;
	while(l<m)
	{
		while(sum<ans1&&r<m)
		{
			r++;
			vis[h2[r]]++;
			if(vis[h2[r]]==1)sum++;
		}
		while(vis[h2[l]]>1)
		{
			vis[h2[l]]--;
			l++;
		}
		if(sum==ans1)ans2=min(ans2,r-l+1);
		vis[h2[l]]--;
		if(vis[h2[l]]==0)sum--;
		l++;
	}
	cout<<ans1<<endl<<ans2<<endl;
	return 0;
}
2021/4/30 18:20
加载中...