自动搬运

查看原文

来自洛谷，原作者为

	louhao088 这个家伙不懒，但还是什么都没留下

搬运于2025-08-24 21:24:27，当前版本为作者最后更新于2020-09-18 21:45:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

很明显，这就是一道 HASH，在这里我们使用 map + string，代码难度就大大下降了。

我们每次记录此时有多少个单词，若比之前多，则直接更新长度与数量。

然后在更新左边 $l$，若最左边的单词不想背，或后文已出现就更新，把长度去最短即可。

时间

$O(m \log m)$，非常优秀。

最短代码

#include<bits/stdc++.h>
using namespace std;
map<string,int>sum;
map<string,bool>flag;
int ans1,ans2,n,m,l;
string s[100005],s1; 
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>s1,flag[s1]=1;//标记单词想不想背
	cin>>m;l=1;
	for(int i=1;i<=m;i++)
	{
		cin>>s[i];
		if(flag[s[i]])sum[s[i]]++;//记录单词出现次数
		if(sum[s[i]]==1)ans1++,ans2=i-l+1;//更新
		while(l<=i)
		{
			if(!flag[s[l]]){l++;continue;}//判断要不要背
			if(sum[s[l]]>=2){sum[s[l]]--,l++;continue;}//有没有重复出现
			break;
		}
		ans2=min(ans2,i-l+1);//更新
	}
	cout<<ans1<<endl<<ans2<<endl;
	return 0;
}

如果有帮到你，请点赞支持，谢谢。