专栏文章

UVA11019 Matrix Matcher

ss06793
UVA11019题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@min00ljb
此快照首次捕获于
2025/12/01 18:20
3 个月前
此快照最后确认于
2025/12/01 18:20
3 个月前
查看原文

题目重述

给你两个矩阵 AA、BB。
问：矩阵 BB 在矩阵 AA 中出现了多少次？

思路

根据数据范围想到可以用哈希来做。
我们可以先去把 BB 矩阵的哈希值算出来：
（以下公式中的变量基本上全部使用代码中的变量，省略取模以使公式简洁）
sum1i,j=sum1i,j−1×h+bi,jsum1i,Y=sum1i−1,Y×z+sum1i,Ysum1_{i,j} = sum1_{i,j-1} \times h + b_{i,j}\\ sum1_{i,Y} = sum1_{i-1,Y} \times z + sum1_{i,Y}
最后 sum1X,Ysum1_{X,Y} 就是 BB 矩阵的哈希值。
我们还要求 AA 的二维哈希前缀和（和 BB 的差不多），然后再求以 (i,j)(i,j) 为右下角的、大小和 BB 相等的每一个哈希值：
val1=sum2i,j−sum2i−X,j×zXval2=sum2i,j−Y−sum2i−X,j−Y×zXval=val1−val2×hYval_1 = sum2_{i,j} - sum2_{i-X,j} \times z^X \\ val_2 = sum2_{i,j-Y} - sum2_{i-X,j-Y} \times z^X \\ val = val1 - val2 \times h^Y
求出 valval 的值后，如果满足 val==sum1[X][Y]，ansans 就加一。

Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e3+10;
const int h1=58324241/*13*/;
const int z1=78324241;
const int h2=88324241;
const int z2=68324233;
const int mod1=883246289;
const int mod2=983246233;
int t,n,m,X,Y,ans;
char a[maxn][maxn];
char b[maxn][maxn];
int sum1[maxn][maxn];
int sum2[maxn][maxn];
int sum3[maxn][maxn];
int nxt[maxn];
int flag[maxn],tot;
int kuai(int x,int y){
	int num=1;
	while(y){
		if(y&1){
			num*=x;
			num%=mod1;
		}
		x*=x;
		x%=mod1;
		y=(y>>1);
	}
	return num;
}
signed main(){
	scanf("%lld",&t);
	while(t--){
		ans=0;
		scanf("%lld%lld",&n,&m);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cin>>a[i][j];
			}
		}
		scanf("%lld%lld",&X,&Y);
		int len=Y;
		for(int i=1;i<=X;i++){
			for(int j=1;j<=Y;j++){
				cin>>b[i][j];
			}
		}
		int inv1=kuai(z1,X);
		int inv2=kuai(h1,Y);
		for(int i=1;i<=X;i++){
			for(int j=1;j<=Y;j++){
				sum1[i][j]=(sum1[i][j-1]*h1+b[i][j]-'a'+1)%mod1;
			}
		}
		for(int i=2;i<=X;i++){
			sum1[i][Y]=(sum1[i-1][Y]*z1+sum1[i][Y])%mod1;
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				sum3[i][j]=(sum3[i][j-1]*h1+a[i][j]-'a'+1)%mod1;
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				sum2[i][j]=(sum2[i-1][j]*z1+sum3[i][j])%mod1;
			}
		}
		for(int i=X;i<=n;i++){
			for(int j=Y;j<=m;j++){
				int val1=((sum2[i][j]-sum2[i-X][j]*inv1%mod1)%mod1+mod1)%mod1;
				int val2=((sum2[i][j-Y]-sum2[i-X][j-Y]*inv1%mod1)%mod1+mod1)%mod1;
				int val=((val1-val2*inv2%mod1)%mod1+mod1)%mod1;
				ans+=(val==sum1[X][Y]);
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...