矩陣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]);