【poj3690】Constellations 哈希

传送门

题目分析

考虑将大矩阵的每个1*q矩阵哈希值求出，然后让小矩阵的第一行在大矩阵中找，如果找到，并且能匹配所有行则出现过。否则没出现过。

在初始化1*q矩阵时可以进行优化：假设该行为123456，要求1*5的矩阵哈希值，可以先暴力求出1~5，为 $1 * H^4 + 2 * H^3 + 3 * H^2 + 4 * H + 5$，现在要删除1添加6：变为$2 * H^4 + 3 * H^3 + 4 * H^2 + 5 * H + 6$，也就是先减去1的哈希值乘以$H^{len - 1}$，然后乘以H，加上6的哈希值。代码如下:

  for(int i = 1; i <= n; i++){
      for(int k = 1; k <= q; k++)
          fixedHash[i][1] = fixedHash[i][1] * H + getVal(matrix[i][k]);
      for(int j = 2; j <= m - q + 1; j++)
          fixedHash[i][j] = (fixedHash[i][j - 1] - getVal(matrix[i][j - 1]) * poww[q - 1]) * H + getVal(matrix[i][j + q - 1]);
  }

 code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

const int N = 1005;
typedef unsigned long long ull;
const ull H = 2;
ull fixedHash[N][N], hash[100], poww[100];
int n, m, T, p, q, k;
char matrix[N][N], small[100][100];

inline int getVal(char x){
    return x == '*' ? 1 : 0;
}

inline bool check(int x, int y){
    for(int k = x + 1; k <= x + p - 1; k++)
        if(fixedHash[k][y] != hash[k - x + 1])
            return false;
    return true;
}

int main(){
    freopen("h.in", "r", stdin);
    poww[0] = 1;
    for(int i = 1; i <= 100; i++) poww[i] = poww[i - 1] * H;
    while(scanf("%d%d%d%d%d", &n, &m, &T, &p, &q), n + m + T + p + q){
        memset(matrix, 0, sizeof matrix);
        for(int i = 1; i <= n; i++) scanf("%s", matrix[i] + 1);
        memset(fixedHash, 0, sizeof fixedHash);
        for(int i = 1; i <= n; i++){
            for(int k = 1; k <= q; k++)
                fixedHash[i][1] = fixedHash[i][1] * H + getVal(matrix[i][k]);
            for(int j = 2; j <= m - q + 1; j++)
                fixedHash[i][j] = (fixedHash[i][j - 1] - getVal(matrix[i][j - 1]) * poww[q - 1]) * H + getVal(matrix[i][j + q - 1]);
        }
        int cnt = 0;
        for(int i = 1; i <= T; i++){
            memset(small, 0, sizeof small);
            for(int j = 1; j <= p; j++)
                scanf("%s", small[j] + 1);
            memset(hash, 0, sizeof hash);
            for(int j = 1; j <= p; j++)
                for(int k = 1; k <= q; k++)
                    hash[j] = hash[j] * H + getVal(small[j][k]);
            bool flag = true;
            for(int j = 1; j <= n - p + 1; j++){
                for(int k = 1; k <= m - q + 1; k++){
                    if(fixedHash[j][k] == hash[1])
                        if(check(j, k)){
                            cnt++;
                            flag = false;
                            break;
                        }
                }
                if(!flag) break;
            }
        }
        printf("Case %d: %d
", ++k, cnt);
    }
}