codevs3013单词背诵

/*

手打的哈希+线性的维护

第一问：hash一下 并且用个h记录某个单词要背的

第二问：线性的跑一边

开始队列里装下前一些单词使这一坨符合要求 并且记录出现次数num

然后开始从前面删

删除的条件：要么是非法的单词（h值为0）

            要么num值大于1

如果删不了就在进来一个 更新num

直到跑完  这过程中每次更新l

注意这样有极端数据 如果第一问答案为 0 需要特判一下

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<map>

#define maxm 100100

#define maxn 100010

#define mod 100007

#define p 17

using namespace std;

char s[maxn][],ss[maxn][];

int n,m,f[maxn],a[maxm],ans,l=maxn;

int h[maxn],num[maxn],vis[maxn],head,tail;

int get_hash(char *str)

{

    int len=strlen(str),hash=;

    for(int i=;i<=len-;i++)

      hash=(hash*p+str[i]-'a')%mod;

    return hash;

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)

      scanf("%s",s[i]);

    scanf("%d",&m);

    for(int i=;i<=m;i++)

      {

          scanf("%s",ss[i]);

        f[get_hash(ss[i])]=;

      }

    for(int i=;i<=n;i++)

      {

          int tmp=get_hash(s[i]);

          if(f[tmp]==)

          {

            ans++;

            h[tmp]=;

          }

      }

    int si=;

    head++;

    while(tail<=m)

      {

          int tmp=get_hash(ss[++tail]);

          if(h[tmp])

          {

              if(vis[tmp]==)

              si++;

              num[tmp]++;

              vis[tmp]=;

          }

          if(si==ans&&si!=)

            {

                int x=get_hash(ss[head]);

                while(head<tail&&(h[x]==||num[x]>))

                  {

                      if(h[x])

                  num[x]--;

                x=get_hash(ss[++head]);

              }

            l=min(l,tail-head+);

          }

      }

    if(ans)printf("%d\n%d\n",ans,l);

    else printf("0\n0");

}