矩阵hash + KMP - UVA 12886 The Big PaintingThe Big Painting Problem's Link: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=88791

Mean: 

给你两个由字符组成的矩阵，让你判断第一个矩阵在第二个矩阵中出现了多少次。

analyse:

典型的二维矩阵hash。

这题有两种做法：

第一种：横向hash，然后纵向KMP。时间复杂度是O(N*(N+M)).

第二种：二维hash。直接对两个矩阵做二维hash，然后判断大矩阵的子矩阵的hash值是否等于小矩阵的hash值，统计答案即可。

从实现上来说，二维hash更容易写，也更容易理解，但是我在比赛时忽略了一种情况：

正确答案是：3.

但如果我们在hash时，横向hash选取的种子值和纵向hash选取的种子值是相同的，就会出现错误，答案就变为了5。

这是因为本来答案只要统计横向的，但是由于横向和纵向的种子值相同，就会多统计进去两次纵向的。

如果题目说小矩形（或者大矩形）可以旋转匹配，那么种子值选取一样就对了。

Time complexity: 二维hash：O(N*M)    hash+KMP：O(N*(N+M))

Source code: 

二维hash:

/*

* this code is made by crazyacking

* Verdict: Accepted

* Submission Date: 2015-08-10-08.37

* Time: 0MS

* Memory: 137KB

*/

#include <queue>

#include <cstdio>

#include <set>

#include <string>

#include <stack>

#include <cmath>

#include <climits>

#include <map>

#include <cstdlib>

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#define  LL long long

#define  ULL unsigned long long

using namespace std;

const int MAXN=2010;

const ULL seed1 = 10000007;  // line   h

const ULL seed2 = 100000007;// row     w

int hp,wp,hm,wm;

char G1[MAXN][MAXN],G2[MAXN][MAXN];

ULL Tab1[MAXN][MAXN],Tab2[MAXN][MAXN],goal;

void GetHash()

{

     goal=0;

     for(int i=0;i<hp;++i)

     {

           ULL a=0;

           for(int j=0;j<wp;++j)

           {

                 a=a*seed2+G1[i][j];

           }

           goal=goal*seed1+a;

     }

}

int solve()

     int ans=0;

     ULL base1=1,base2=1;

     for(int i=0;i<hp;++i) base1*=seed1;

     for(int i=0;i<wp;++i) base2*=seed2;

     for(int i=0;i<hm;++i) // line

           for(int j=0;j<wp;++j) a=a*seed2+G2[i][j];

           Tab1[i][wp-1]=a;

           for(int j=wp;j<wm;++j)

                 Tab1[i][j]=Tab1[i][j-1]*seed2 + G2[i][j] -base2*G2[i][j-wp];

     for(int i=wp-1;i<wm;++i)

           for(int j=0;j<hp;++j) a=a*seed1+Tab1[j][i];

           Tab2[hp-1][i]=a;

           if(a==goal) ++ans;

           for(int j=hp;j<hm;++j)

                 Tab2[j][i]=Tab2[j-1][i]*seed1 +Tab1[j][i] -Tab1[j-hp][i]*base1;

                 if(Tab2[j][i]==goal) ++ans;

     return ans;

int main()

     ios_base::sync_with_stdio(false);

     cin.tie(0);

     while(~scanf("%d %d %d %d",&hp,&wp,&hm,&wm))

           getchar();

           for(int i=0;i<hp;++i) gets(G1[i]);

           for(int i=0;i<hm;++i) gets(G2[i]);

           GetHash();

           printf("%d\n",solve());

     return 0;

hash+KMP:

* Submission Date: 2015-08-09-13.27

const int MAXN = 2010;

const ULL seed =1000000007;

ULL base[MAXN];

ULL hashval[MAXN][MAXN],Ti[MAXN][MAXN],hashTmp[MAXN],val[MAXN];

int Next[MAXN],h,w,n,m;

char s[MAXN][MAXN],t[MAXN][MAXN];

int KMP()

     for(int i=0,j=-1;i<m;++i)

           while(j!=-1 && val[i]!=hashTmp[j+1]) j=Next[j];

           if(val[i]==hashTmp[j+1])

                 if(++j==w-1)

                 {

                       j=Next[j];

                       ans++;

                 }

void init(char s[MAXN][MAXN],ULL hashval[MAXN][MAXN],int h,int w)

     for(int j=0;j<w;++j)

           hashval[h][j]=0;

           for(int i=h-1;i>=0;--i) hashval[i][j]=hashval[i+1][j]*seed+s[i][j];

     init(s,hashval,h,w);

     init(t,Ti,n,m);

     for(int i=0;i<w;++i)

           hashTmp[i]=hashval[0][i];

     // KMP Matching

     Next[0]=-1;

//      puts("- - - - - - - - - - - Program Run Here ! - - - - - - - - - - - - ");

     for(int i=1,j=-1;i<w;++i)

           while(j!=-1 && hashTmp[i]!=hashTmp[j+1]) j=Next[j];

           Next[i]=hashTmp[i]==hashTmp[j+1]? ++j:j;

//      for(int i=1;i<w;++i)

//      {

//            printf("%d",Next[i]);

//      }

     for(int i=0;i<n-h+1;++i)

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

                 val[j]=Ti[i][j]-Ti[i+h][j]*base[h];

           ans+=KMP();

void _()

     base[0]=1;

     for(int i=1;i<MAXN;++i) base[i]=base[i-1]*seed;

     _();

     while(~scanf("%d %d %d %d",&h,&w,&n,&m))

           for(int i=0;i<h;++i) gets(s[i]);

           for(int i=0;i<n;++i) gets(t[i]);