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写法。

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

不过碰撞的几率很小。

 1 ull p=0;
 2         for (int i=0;i<x;i++)
 3         {
 4             ull tmp=0;
 5             for (int j=0;j<y;j++)
 6             tmp=tmp*B1+s1[i][j];
 7             p=p*B2+tmp;
 8         }
 9 
10 
11         ull t=1;
12         int ans=0;
13 
14         for (int i=0;i<y;i++) t*=B1;
15         for (int i=0;i<n;i++)
16         {
17             ull a=0;
18             for (int j=0;j<y;j++) a=a*B1+s[i][j];
19             mp[i][y-1]=a;
20             for (int j=y;j<=m;j++)
21             mp[i][j]=mp[i][j-1]*B1-s[i][j-y]*t+s[i][j];
22         }
23         t=1;
24         for (int i=0;i<x;i++) t*=B2;
25 
26         for (int i=y-1;i<=m;i++)
27         {
28             ull tmp=0;
29             for (int j=0;j<x;j++) tmp=tmp*B2+mp[j][i];
30             mpp[x-1][i]=tmp;
31             if (tmp==p) ans++;
32             for (int j=x;j<n;j++)
33             {
34                 mpp[j][i]=mpp[j-1][i]*B2-mp[j-x][i]*t+mp[j][i];
35                 if (mpp[j][i]==p) ans++;
36             }

View Code