洛谷 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数组中。然后核对标记，就可以求出第一问了。
第二问是本题的难点。
如何求出一个最短的符合要求的序列长度呢？
暴力的思路是区间枚举左右端点，核对是否符合条件。但是这样做显然不行，于是我们想到用尺取法优化区间枚举。
关于尺取法，如有不太了解的请移步本蒟蒻的总结博客：
了解了尺取法的基本内涵。针对于这道题，我们利用尺取的实现过程是这样的：
因为我们已经求得了第一问的答案，那么我们需要用这个已知答案来确定这个区间是否是可行的解。具体操作方法是：建立一个(appear[])数组，存每个单词（当然是他们的哈希值）出现的次数。如果这个词是第一次出现，那么显然目前区间中的单词数量应该加一。同时，如果这个词出现的次数要是大于等于1的话，那么就尝试进行舍去，看一下有没有更优的选择。
这个地方会比较难理解：我把它叫做”不能偏安一隅“，我们不能只是在(appear[])大于1的时候舍去这个点，等于1的时候一样要舍，为什么呢？就是因为，假如你选择了这个单词作为区间中唯一出现的目标单词，但是它和区间中距离它最近的另一个目标单词非常远，但是区间外面还有一个单词，和距离它最近的目标单词超级近。这个时候你应该选哪一种呢？显而易见，那个更近的对答案的贡献是更优的。所以，我们要在(appear[])等于1的时候也进行舍去，然后继续扫描。因为这个时候的(ans)已经被更新了，所以我们不愁答案错误。
然后就求得了第二问的答案。
总的来说，这道题的思路还是比较清晰的，并没有什么太大的难点。主要是尺取法部分的代码实现。以及，提醒大家，数组的大小要开的和模数一样大，否则就会有几率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
",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;
}