POJ 3690

发表于 |

题目

给$T$个$P \times Q$的矩阵。问其中有多少个在$N\times M$的矩阵中出现过。
矩阵中元素只有2种。

数据范围

$1\leq N,M\leq 1000,1\leq P,Q\leq 50,1 \leq T\leq 100$

做法

滚动Hash

对$T$个矩阵进行二维的Hash，再对$N\times M$的矩阵中的$P\times Q$大小的子矩阵进行Hash,统计个数即可。

本题Hash用的是滚动Hash，行和列取的基数$B$不相同，并且模数取为$2^{64}$，用自然溢出省略取模操作。

前缀Hash

计算二维Hash前缀，其余方法同上。

代码

滚动Hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
typedef unsigned long long ull;
const int MAX_NM = 1005;
const int MAX_PQ = 55;
const int MAX_T = 105;
int N, M, T, P, Q;
char field[MAX_NM][MAX_NM];
char patterns[MAX_T][MAX_NM][MAX_NM];
ull hsh[MAX_NM][MAX_NM], tmp_hsh[MAX_NM][MAX_NM];
void ComputeHash(char a[MAX_NM][MAX_NM], int n, int m)
{
  const ull B1 = 1e9 + 9;
  const ull B2 = 1e9 + 7;
  ull t1 = 1;
  for (int i = 0; i < Q; ++i) t1 *= B1;
  for (int i = 0; i < n; ++i) {
    ull e = 0;
    for (int j = 0; j < Q; ++j) {
      e = e * B1 + a[i][j];
    }
    for (int j = 0; j + Q <= m; ++j) {
      tmp_hsh[i][j] = e;
      if (j + Q < m) e = e * B1 - a[i][j] * t1 + a[i][j + Q];
    }
  }
  ull t2 = 1;
  for (int i = 0; i < P; ++i) t2 *= B2;
  for (int j = 0; j + Q <= m; ++j) {
    ull e = 0;
    for (int i = 0; i < P; ++i) {
      e = e * B2 + tmp_hsh[i][j];
    }
    for (int i = 0; i + P <= n; ++i) {
      hsh[i][j] = e;
      if (i + P < n) e = e * B2 - t2 * tmp_hsh[i][j] + tmp_hsh[i + P][j];
    }
  }
}
int solve()
{
  multiset<ull> S;
  for (int i = 0; i < T; ++i) {
    ComputeHash(patterns[i], P, Q);
    S.insert(hsh[0][0]);
  }
  ComputeHash(field, N, M);
  for (int i = 0; i + P <= N; ++i) {
    for (int j = 0; j + Q <= M; ++j) {
      S.erase(hsh[i][j]);
    }
  }
  return T - S.size();
}
int main()
{
  int ncase = 0;
  while (scanf("%d%d%d%d%d", &N, &M, &T, &P, &Q), N || M || T || P || Q) {
    for (int i = 0; i < N; ++i) {
      scanf("%s", field[i]);
    }
    for (int t = 0; t < T; ++t) {
      for (int i = 0; i < P; ++i) {
        scanf("%s", patterns[t][i]);
      }
    }
    printf("Case %d: %d\n", ++ncase, solve());
  }
  return 0;
}

前缀Hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
typedef long long ll;
const int MAX_SIZE = 1005;
const int MAX_T = 105;
const ll P1 = 23456789;
// const ll P1 = 13131;
const ll P2 = 19961993;
// const ll P2 = 1313;
const ll MOD = 1e9 + 7;
int N, M, T, P, Q;
int ncase;
char field[MAX_SIZE][MAX_SIZE];
char patterns[MAX_T][MAX_SIZE][MAX_SIZE];
ll pow_P1[MAX_SIZE], pow_P2[MAX_SIZE];
ll hsh_xy[MAX_SIZE][MAX_SIZE], hsh_x[MAX_SIZE][MAX_SIZE];
void CalHash(char a[MAX_SIZE][MAX_SIZE], int n, int m)
{
  for (int i = 1; i <= n; ++i) {
    hsh_x[i][0] = 0;
    for (int j = 1; j <= m; ++j) {
      hsh_x[i][j] = (hsh_x[i][j - 1] * P1 + a[i - 1][j - 1]) % MOD;
    }
  }
  for (int j = 1; j <= m; ++j) {
    hsh_xy[0][j] = 0;
    for (int i = 1; i <= n; ++i) {
      hsh_xy[i][j] = (hsh_xy[i - 1][j] * P2 + hsh_x[i][j]) % MOD;
    }
  }
}
inline ll GetHash(int x1, int y1, int x2, int y2)
{
  ll tmp = hsh_xy[x2][y2]
         + hsh_xy[x1 - 1][y1 - 1] * pow_P1[y2 - y1 + 1] % MOD * pow_P2[x2 - x1 + 1] % MOD
         - hsh_xy[x2][y1 - 1] * pow_P1[y2 - y1 + 1] % MOD
         - hsh_xy[x1 - 1][y2] * pow_P2[x2 - x1 + 1] % MOD;
  tmp = (tmp % MOD + MOD) % MOD;
  return tmp;
}
void solve()
{
  multiset<ll> S;
  for (int i = 0; i < T; ++i) {
    CalHash(patterns[i], P, Q);
    S.insert(hsh_xy[P][Q]);
  }
  CalHash(field, N, M);
  for (int i = 0; i + P <= N; ++i) {
    for (int j = 0; j + Q <= M; ++j) {
      S.erase(GetHash(i + 1, j + 1, i + P, j + Q));
    }
  }
  printf("Case %d: %d\n", ++ncase, T - (int)S.size());
}
int main()
{
  pow_P1[0] = 1; pow_P2[0] = 1;
  for (int i = 1; i < MAX_SIZE; ++i) {
    pow_P1[i] = pow_P1[i - 1] * P1 % MOD;
    pow_P2[i] = pow_P2[i - 1] * P2 % MOD;
  }
  while (scanf("%d%d%d%d%d", &N, &M, &T, &P, &Q), N || M || T || P || Q) {
    for (int i = 0; i < N; ++i) {
      scanf("%s", field[i]);
    }
    for (int i = 0; i < T; ++i) {
      for (int j = 0; j < P; ++j) {
        scanf("%s", patterns[i][j]);
      }
    }
    solve();
  }
  return 0;
}