本文共 2664 字，大约阅读时间需要 8 分钟。

字符串哈希(二维)-Constellations POJ - 3690

$公式推导$——《》

题意：

$$\begin{gathered} 输入一个n\times m的{由}^{\prime }{\ast }^{\prime }{和}^{\prime }{0}^{\prime }构成的矩阵M_0，接着输入q个a\times b的矩阵(a<=n,b<=m)， \\ 求这q个矩阵中，有多少个矩阵是M_0的子矩阵。 \end{gathered}$$

样例及数据范围：

具体落实：

$$\begin{gathered} ①、可以在输入n\times m的矩阵的同时，对其每一行单独进行哈希，为③预处理准备。 \\ ②、再求q个小矩阵的哈希值，用multiset来保存。 \\ ③、然后求整个n\times m的矩阵中所有的a\times b的子矩阵的哈希值，同时在multiset中删除对应的元素。 \\ ④、最后multiset中剩下没有被删掉的元素就是未能匹配成功的子矩阵， \\ 答案为输入的子矩阵的个数q减去容器中剩余元素的个数。 \end{gathered}$$

$$\begin{gathered} 因为POJ不支持unordered\_set，所以本题采用了multiset。 \\ 另外，unsignedint处理起来要比unsignedlonglong要快一些，但冲突概率会大一些。 \end{gathered}$$

$神奇发现：似乎对容器只进行删除插入操作要比询问要快...$

代码：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #define ull unsigned intusing namespace std;const int N=1010;const int base=131;int n,m,q,a,b;ull h[N][N],p[2510];char str[N];ull get(ull h[],int l,int r){
       return h[r]-h[l-1]*p[r-l+1];}int main(){
       int T=1;    while(~scanf("%d%d%d%d%d",&n,&m,&q,&a,&b),n||m||q||a||b)    {
           multiset
        
          S; for(int i=1;i<=n;i++) { scanf("%s",str+1); for(int j=1;j<=m;j++) h[i][j]=h[i][j-1]*base+str[j]-'0'; } p[0]=1; for(int i=1;i<=a*b;i++) p[i]=p[i-1]*base; for(int k=1;k<=q;k++) { ///计算输入的子矩阵的值 ull s=0; for(int i=1;i<=a;i++) { scanf("%s",str+1); for(int j=1;j<=b;j++) s=s*base+str[j]-'0'; } S.insert(s); } ///j枚举右端点,求所有a×b的子矩阵哈希值 for(int j=b;j<=m;j++) { ull s=0; int l=j-b+1,r=j; for(int i=1;i<=n;i++) ///按列求哈希 { s=s*p[b]+get(h[i],l,r); if(i-a>0) s-=get(h[i-a],l,r)*p[a*b]; if(i-a>=0) S.erase(s); } } printf("Case %d: %d\n",T++,q-S.size()); } return 0;}
        
       
      
     
    
   

转载地址：http://bjor.baihongyu.com/