题解 P1381 【单词背诵】

· · 题解

来自一名离csp二轮只有半周时间了才学会哈希的蒟蒻的题解

翻了下题解，看到大佬们都是差不多都是单哈希加map（当然也有很多用别的骚方法的大佬ORZ），还没有一个用双哈希的。

个人不是很熟悉map（都要二轮了等会儿还是去学一学），而且多单哈希总有一种觉得不稳的感觉，喜欢用双哈希。而双哈希配合Map的话对我这个不熟悉map的蒟蒻更是难上加难（话说真的有二维map这种东西吗。。）。

所以就自己写了一个:

双哈希，排序+lowerbound实现map的效果，最后尺取法解决第二问。

都开始做这道题的应该都已经熟悉hash操作了吧,本蒟蒻在这里就不再赘述了，想学的可以去哈希模板

具体细节实现看代码吧。

附上巨丑代码一份：

#include<bits/stdc++.h>
#define base 131
#define int unsigned long long      //懒鬼写法(搭配signed main使用) 
using namespace std;
struct node
{
    int x,y;//两个不同的哈希值 
    friend bool operator < (node x,node y)//以x为第一关键字排序 
    {
        return x.x<y.x;
    }
}a[1005];//储存单词表 
int cnt[1005];//尺取法当前区间内每个单词(以下标表示)出现的次数 
int b[100005];//储存1文章中对应单词的位置 
bool vis[1005];
int HSH(string s,int mod)//标准的哈希 
{
    int ans=0;
    int sz=s.size();
    for(int i=0;i<sz;i++)
    {
        ans=(ans*base+s[i])%mod;
    }
    return ans;
}
signed main()
{
    int n,ans1=0,ans2=1000000;
    cin>>n;
    string tmp;
    for(int i=1;i<=n;i++)
    {
        cin>>tmp;
        a[i].x=HSH(tmp,1e9+7);
        a[i].y=HSH(tmp,1e9+9);//哈希处理 
    }
    sort(a+1,a+n+1);//排序以便lowerbound对照下标 
    int m;
    cin>>m;
    for(int i=1;i<=m;i++) 
    {
        cin>>tmp;
        node tsh=node{HSH(tmp,1e9+7),HSH(tmp,1e9+9)};
        int p=lower_bound(a+1,a+n+1,tsh)-a;//p表示文章中该单词在单词表中的位置（但有可能单词表中没有)
        bool flag=0;//记录到底有没有这个单词 
        for(;;p++)
        {
            if(a[p].x==tsh.x)//如果第一维相同 
            {   
                if(a[p].y==tsh.y)//第二维也相同，那就差不多是一个了（这都能撞到两个就真是见鬼了。。。） 
                {
                    b[i]=p;//记录位置 
                    if(!vis[p])
                    {
                        vis[p]=1;
                        ans1++;
                    }
                    flag=1;
                    break;
                }
                //可能存在第一位相同第二维不同的情况，这个时候我们找下一个位置 
            }
            else//第一维都不同 
                break;//那就肯定不行了 
        }
        if(!flag)
        {
            b[i]=n+1;//没找到的话就把他的对应下标放到n+1 
        }
    }
    cnt[n+1]=10000000;//不存在的东西无论是进了尺取法范围还是出了尺取法范围都不应该影响计数 
    for(int i=1,cntn=0/*统计当前有几种单词*/,l=1/*左指针*/;i<=m;i++)
    {
        if(!cnt[b[i]])//如果这个单词未出现过 
        {
            cntn++;//单词种类数+1 
        }
        cnt[b[i]]++;//这种单词的数量+1 
        while(cnt[b[l]]>1)//如果区间开头那个单词是多余的（也就是在后面还会出现） 
        {
            cnt[b[l]]--;//就删去它 
            l++;//并移动左指针 
        }
        if(cntn==ans1)//已经出现了全部单词 
        {
            ans2=min(ans2,i-l+1);//计算答案 
        }
    }
    cout<<ans1<<endl<<(ans2==1000000?0:ans2);//如果ans2无法更新，再特别输出一下 
    return 0;
}