AcWing - 156 矩阵（二维哈希）

传送门：AcWing - 156

思路分析

二维哈希模板

AC代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) (x)&(-x)
#define sz(x) (int)(x).size()
#define each(a,x) for(auto& a:x)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f;
const double PI = acos(-1);

const int N = 1111;


ull h[N][N],ba[2][N],p[2];
char s[N];

ull get(int x1,int y1,int x2,int y2){
    ull ans = h[x2][y2]-h[x1-1][y2]*ba[0][x2-x1+1]-h[x2][y1-1]*ba[1][y2-y1+1]+h[x1-1][y1-1]*ba[0][x2-x1+1]*ba[1][y2-y1+1];
    return ans;
}

signed main() {

#ifdef xiaofan
    clock_t stTime = clock();
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
/*==========================begin============================*/
    IOS;
    ba[0][0] = 1;
    ba[1][0] = 1;
    p[0] = 13331;
    p[1] = 1e9+7;
    int n,m,a,b;
    cin>>n>>m>>a>>b;
    for(int i=1;i<N;i++) {
        ba[0][i] = ba[0][i-1]*p[0];
        ba[1][i] = ba[1][i-1]*p[1];
    }
    unordered_set<ull>S;
    for(int i=1;i<=n;i++){
        cin>>s+1;
        for(int j=1;j<=m;j++){
            h[i][j] = h[i-1][j]*p[0]+h[i][j-1]*p[1]-h[i-1][j-1]*p[0]*p[1]+(int)s[j]+1;
            if(i>=a && j>=b) S.insert(get(i-a+1,j-b+1,i,j));
        }
    }
    h[0][0] = 0;
    int q;
    cin>>q;
    while(q--){
        for(int i=1;i<=a;i++){
            cin>>s+1;
            for(int j=1;j<=b;j++){
                h[i][j] = h[i-1][j]*p[0]+h[i][j-1]*p[1]-h[i-1][j-1]*p[0]*p[1]+(int)s[j]+1;
            }
        }
        cout<<S.count(h[a][b])<<"\n";
    }



/*===========================end=============================*/
#ifdef xiaofan
    cerr << "Time Used:" << clock() - stTime << "ms" <<endl;
#endif
    return 0;
}