The Big Painting

viewProblem.action?id=88791

Mean:

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

analyse:

典型的二维矩阵hash。

这题有两种做法：

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

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

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

xo

xoxo

oxox

正确答案是：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=;
const ULL seed1 = ; // line h
const ULL seed2 = ;// 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=;
for(int i=;i<hp;++i)
{
ULL a=;
for(int j=;j<wp;++j)
{
a=a*seed2+G1[i][j];
}
goal=goal*seed1+a;
}
}

int solve()
{
int ans=;
ULL base1=,base2=;
for(int i=;i<hp;++i) base1*=seed1;
for(int i=;i<wp;++i) base2*=seed2;
for(int i=;i<hm;++i) // line
{
ULL a=;
for(int j=;j<wp;++j) a=a*seed2+G2[i][j];
Tab1[i][wp-]=a;
for(int j=wp;j<wm;++j)
{
Tab1[i][j]=Tab1[i][j-]*seed2 + G2[i][j] -base2*G2[i][j-wp];
}
}
for(int i=wp-;i<wm;++i)
{
ULL a=;
for(int j=;j<hp;++j) a=a*seed1+Tab1[j][i];
Tab2[hp-][i]=a;
if(a==goal) ++ans;
for(int j=hp;j<hm;++j)
{
Tab2[j][i]=Tab2[j-][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();
while(~scanf("%d %d %d %d",&hp,&wp,&hm,&wm))
{
getchar();
for(int i=;i<hp;++i) gets(G1[i]);
for(int i=;i<hm;++i) gets(G2[i]);
GetHash();
printf("%d\n",solve());
}
return ;
}
/*

hash+KMP:

/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-08-09-13.27
* 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 = ;
const ULL seed =;
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()
{
int ans=;
for(int i=,j=-;i<m;++i)
{
while(j!=- && val[i]!=hashTmp[j+]) j=Next[j];
if(val[i]==hashTmp[j+])
{
if(++j==w-)
{
j=Next[j];
ans++;
}
}
}
return ans;
}

void init(char s[MAXN][MAXN],ULL hashval[MAXN][MAXN],int h,int w)
{
for(int j=;j<w;++j)
{
hashval[h][j]=;
for(int i=h-;i>=;--i) hashval[i][j]=hashval[i+][j]*seed+s[i][j];
}
}

int solve()
{
init(s,hashval,h,w);
init(t,Ti,n,m);
for(int i=;i<w;++i)
{
hashTmp[i]=hashval[][i];
}
// KMP Matching
Next[]=-;
// puts("- - - - - - - - - - - Program Run Here ! - - - - - - - - - - - - ");

for(int i=,j=-;i<w;++i)
{
while(j!=- && hashTmp[i]!=hashTmp[j+]) j=Next[j];
Next[i]=hashTmp[i]==hashTmp[j+]? ++j:j;
}
// for(int i=1;i<w;++i)
// {
// printf("%d",Next[i]);
// }
int ans=;
for(int i=;i<n-h+;++i)
{
for(int j=;j<m;++j)
val[j]=Ti[i][j]-Ti[i+h][j]*base[h];
ans+=KMP();
}
return ans;
}

void _()
{
base[]=;
for(int i=;i<MAXN;++i) base[i]=base[i-]*seed;
}
int main()
{
_();
while(~scanf("%d %d %d %d",&h,&w,&n,&m))
{
getchar();
for(int i=;i<h;++i) gets(s[i]);
for(int i=;i<n;++i) gets(t[i]);
printf("%d\n",solve());
}
}

巴特西

矩阵hash + KMP - UVA 12886 The Big Painting

The Big Painting

Problem's Link: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=88791

最新文章

热门文章