1：

UVa 10887 - Concatenation of Languages

map 可以做，但是输入实在恶心，有空串之类的HASH模板：

int Hash(char *s)
{
   int seed=131,sum=0;
   while (*s)
   sum=sum*seed+(*s++);
   return (sum&0x7FFFFFFF)%N;
}

void hash_insert(int s)
{
   int h=Hash(c[s]);
   int u=head[h];
   while (u)
   {
     if (!strcmp(c[s],c[u]))
     {
      return;
     }
     u=next[u];
   }
   next[s]=head[h];
   head[h]=s;
   ++ans;
}虽然简单，但是要灵活用好也比较费力。

UVA :Matrix Matcher

一般矩阵串里面找存在目标字串多少次的hash写法。

虽然自然溢出的算法会碰撞的几率很小，但是还是有的，所以这是你没想到更好的解法的时候碰一下运气的做法。

不过碰撞的几率很小。

 ull p=;

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

         {

             ull tmp=;

             for (int j=;j<y;j++)

             tmp=tmp*B1+s1[i][j];

             p=p*B2+tmp;

         }

         ull t=;

         int ans=;

         for (int i=;i<y;i++) t*=B1;

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

         {

             ull a=;

             for (int j=;j<y;j++) a=a*B1+s[i][j];

             mp[i][y-]=a;

             for (int j=y;j<=m;j++)

             mp[i][j]=mp[i][j-]*B1-s[i][j-y]*t+s[i][j];

         }

         t=;

         for (int i=;i<x;i++) t*=B2;

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

         {

             ull tmp=;

             for (int j=;j<x;j++) tmp=tmp*B2+mp[j][i];

             mpp[x-][i]=tmp;

             if (tmp==p) ans++;

             for (int j=x;j<n;j++)

             {

                 mpp[j][i]=mpp[j-][i]*B2-mp[j-x][i]*t+mp[j][i];

                 if (mpp[j][i]==p) ans++;

             }

巴特西

几道hash题

UVa 10887 - Concatenation of Languages

最新文章

热门文章