题解 P1381 【单词背诵】
louhao088
·
·
题解
思路
很明显，这就是一道 HASH，在这里我们使用 map + string，代码难度就大大下降了。
我们每次记录此时有多少个单词，若比之前多，则直接更新长度与数量。
然后在更新左边 l，若最左边的单词不想背，或后文已出现就更新，把长度去最短即可。
时间
## 最短代码
```cpp
#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;
}
```
如果有帮到你，请点赞支持，谢谢。