UVA11019 Matrix Matcher

· · 题解

题目重述

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

思路

根据数据范围想到可以用哈希来做。
我们可以先去把 B 矩阵的哈希值算出来：
（以下公式中的变量基本上全部使用代码中的变量，省略取模以使公式简洁）

sum1_{i,j} = sum1_{i,j-1} \times h + b_{i,j}\\ sum1_{i,Y} = sum1_{i-1,Y} \times z + sum1_{i,Y}

最后 sum1_{X,Y} 就是 B 矩阵的哈希值。
我们还要求 A 的二维哈希前缀和（和 B 的差不多），然后再求以 (i,j) 为右下角的、大小和 B 相等的每一个哈希值：

val_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

求出 val 的值后，如果满足 val==sum1[X][Y]，ans 就加一。

Code

#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;
}