洛谷 P1381 单词背诵

洛谷 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;

题解:

字符串哈希加尺取法枚举区间。

我不会告诉你这俩知识点我都是现学的

一开始的思路约等于没有思路:挨个枚举,逐字符匹配(憨批),区间枚举。后来发现恶心的要命,根本连打的勇气都没有。

于是字符串哈希上场了。我对哈希的理解就是把一个字符串变成一个数,简化字符串匹配的过程。

关于哈希,如有不会请移步本蒟蒻的总结博客:

浅谈字符串Hash

这样的话,我们把要背的字符串的哈希值存到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;
}
上一篇:448. Find All Numbers Disappeared in an Array


下一篇:执行git命令时出现fatal: 'origin' does not appear to be a git repository错误