洛谷 P1381 单词背诵
题目描述
灵梦有n个单词想要背,但她想通过一篇文章中的一段来记住这些单词。
文章由m个单词构成,她想在文章中找出连续的一段,其中包含最多的她想要背的单词(重复的只算一个)。并且在背诵的单词量尽量多的情况下,还要使选出的文章段落尽量短,这样她就可以用尽量短的时间学习尽可能多的单词了。
输入格式
第1行一个数n,
接下来n行每行是一个长度不超过10的字符串,表示一个要背的单词。
接着是一个数m,
然后是m行长度不超过10的字符串,每个表示文章中的一个单词。
输出格式
输出文件共2行。第1行为文章中最多包含的要背的单词数,第2行表示在文章中包含最多要背单词的最短的连续段的长度。
输入输出样例
输入 #1复制
输出 #1复制
说明/提示
【数据范围】
对于30%的数据 n<=50,m<=500;
对于60%的数据 n<=300,m<=5000;
对于100%的数据 n<=1000,m<=100000;
题解:
字符串哈希加尺取法枚举区间。
我不会告诉你这俩知识点我都是现学的。
一开始的思路约等于没有思路:挨个枚举,逐字符匹配(憨批),区间枚举。后来发现恶心的要命,根本连打的勇气都没有。
于是字符串哈希上场了。我对哈希的理解就是把一个字符串变成一个数,简化字符串匹配的过程。
关于哈希,如有不会请移步本蒟蒻的总结博客:
这样的话,我们把要背的字符串的哈希值存到a数组中,并打上标记。把文章字符串的哈希值存到b数组中。然后核对标记,就可以求出第一问了。
第二问是本题的难点。
如何求出一个最短的符合要求的序列长度呢?
暴力的思路是区间枚举左右端点,核对是否符合条件。但是这样做显然不行,于是我们想到用尺取法优化区间枚举。
关于尺取法,如有不太了解的请移步本蒟蒻的总结博客:
然后就求得了第二问的答案。
总的来说,这道题的思路还是比较清晰的,并没有什么太大的难点。主要是尺取法部分的代码实现。以及,提醒大家,数组的大小要开的和模数一样大,否则就会有几率RE...
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=1010;
const int maxm=1e5+10;
const int mod=1e6;
const int p=31;
const int INF=1e9;
int n,m,cnt,ans=INF,l,r;
int a[maxn],b[maxm],appear[mod];
char input[110];
bool need[mod],v[mod];
int hash(char s[])
{
int len=strlen(s);
ll ret=0;
for(int i=0;i<=len;i++)
{
ret*=p,ret+=s[i]-'a';
ret%=mod;
}
return ret%=mod;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",input);
a[i]=hash(input);
need[a[i]]=1;
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%s",input);
b[i]=hash(input);
if(need[b[i]] && !v[b[i]])
cnt++,v[b[i]]=1;
}
if(!cnt)
{
puts("0");
puts("0");
return 0;
}
else
printf("%d\n",cnt);
l=1,r=1;
while(1)
{
if(cnt)
{
if(r>m)
break;
if(need[b[r]])
{
if(!appear[b[r]])
cnt--;
appear[b[r]]++;
}
r++;
}
else
{
while(!need[b[l]])
l++;
if(l>m)
break;
ans=min(ans,r-l);
if(appear[b[l]]==1)
cnt++;
if(appear[b[l]]>=1)
appear[b[l]]--,l++;
}
}
printf("%d",ans);
return 0;
}