哈希&哈希表（2019.6.21训练）

哈希能做的题，map<string,int>vis都能做，我先把map解法写了，有空再研究字符串哈希…（好吧其实就是不想学hash ）

洛谷 P1381 单词背诵

#include <bits/stdc++.h>
using namespace std;
int n,m,l,r,sum,ans1,ans2;
string a[1010],b[100010];
map<string,int>vis,flag;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        vis[a[i]]=1;
    }
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>b[i];
        if(vis[b[i]]&&!flag[b[i]])
        {
            flag[b[i]]=1;
            ans1++;
        }
    }
    if(ans1==0){printf("0\n0\n");return 0;}
    vis.clear();
    ans2=0x3f3f3f3f;
    for(l=1,r=1;r<=m;r++)
    {
        vis[b[r]]++;
        if(vis[b[r]]==1&&flag[b[r]])sum++;
        if(sum<ans1)continue;
        while(l<r&&vis[b[l]]>1||!flag[b[l]]){vis[b[l]]--;l++;}
        ans2=min(ans2,r-l+1);
    }
    printf("%d\n%d\n",ans1,ans2);
    return 0;
}

洛谷 P2957 谷仓里的回声

#include<bits/stdc++.h>
using namespace std;
string a,b;
int main()
{
    cin>>a>>b;
    for(int i=a.size()-1;i>=0;i--)
        for(int j=0;j<=a.size()-i;j++)
        {
            string c=a.substr(j,i);
            if(b.find(c)!=-1)
            {cout<<i;return 0;}
        }
}

洛谷 P3370 【模板】字符串哈希

#include <bits/stdc++.h>
using namespace std;
string a;
int n,ans;
map<string,int>vis;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        if(!vis[a]){ans++;vis[a]=1;}
    }
    printf("%d\n",ans);
    return 0;
}