题目链接：

http://acm.hust.edu.cn/vjudge/problem/129730

The Big Painting

Time Limit: 5000MS

题意

给你一个模板串和待匹配串，问模板串在待匹配串中出现的次数（这里的串是二维矩阵）

题解

每一行做前缀和哈希。

统计的时候先按列再按行，这样在做行的话我们可以利用滚动的形式，计算纵向的哈希值（既总的哈希值）

代码

#include<map>

#include<cmath>

#include<queue>

#include<vector>

#include<cstdio>

#include<string>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define X first

#define Y second

#define mkp make_pair

#define lson (o<<1)

#define rson ((o<<1)|1)

#define mid (l+(r-l)/2)

#define sz() size()

#define pb(v) push_back(v)

#define all(o) (o).begin(),(o).end()

#define clr(a,v) memset(a,v,sizeof(a))

#define bug(a) ;//cout<<#a<<" = "<<a<<endl

#define rep(i,a,b) for(int i=a;i<(b);i++)

typedef long long LL;

typedef vector<int> VI;

typedef pair<int,int> PII;

typedef vector<pair<int,int> > VPII;

const int INF=0x3f3f3f3f;

const LL INFL=0x3f3f3f3f3f3f3f3fLL;

const double eps=1e-8;

//start----------------------------------------------------------------------

const int maxn=2020;

//P进制哈希

const int P=123;

unsigned long long H[maxn][maxn],xp[maxn*maxn],Val;

int n1,m1,n2,m2;

char s1[maxn][maxn],s2[maxn][maxn];

//预处理出位权

void pre() {

	xp[0]=1;

	rep(i,1,maxn*maxn) xp[i]=xp[i-1]*P;

}

//处理前缀和的哈希值

void get_H() {

	Val=0;

	rep(i,1,n1+1) rep(j,1,m1+1) {

		Val=Val*P+(s1[i][j]-'a'+1);

	}

	clr(H,0);

	rep(i,1,n2+1) rep(j,1,m2+1) {

		H[i][j]=H[i][j-1]*P+(s2[i][j]-'a'+1);

	}

}

//枚举，匹配

void solve() {

	int ans=0;

	for(int j=1; j<=m2-m1+1; j++) {

		unsigned long long tmp=0,tmp2=0;

		int lj=j-1,rj=j+m1-1;

		int i;

		for(i=1;i<=n1;i++){

			tmp=tmp*xp[m1]+H[i][rj]-H[i][lj]*xp[m1];

		}

		do{

			if(Val==tmp) ans++;

			tmp-=(H[i-n1][rj]-H[i-n1][lj]*xp[m1])*xp[m1*(n1-1)];

			tmp=tmp*xp[m1]+H[i][rj]-H[i][lj]*xp[m1];

			i++;

		}while(i<=n2+1);

	}

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

}

int main() {

	pre();

	while(scanf("%d%d%d%d",&n1,&m1,&n2,&m2)==4&&n1) {

		rep(i,1,n1+1) scanf("%s",s1[i]+1);

		rep(i,1,n2+1) scanf("%s",s2[i]+1);

		get_H();

		solve();

	}

	return 0;

}

//end-----------------------------------------------------------------------

/*

4 4 10 10

oxxo

xoox

xoox

oxxo

xxxxxxoxxo

oxxoooxoox

xooxxxxoox

xooxxxoxxo

oxxoxxxxxx

ooooxxxxxx

xxxoxxoxxo

oooxooxoox

oooxooxoox

xxxoxxoxxo

*/

巴特西

UVALive - 6893 The Big Painting 字符串哈希

题目链接：

The Big Painting

题意

题解

代码

最新文章

热门文章