[Algorithm] cpp 백준 10538번: 빅 픽쳐 - 2D 롤링 해시로 O(HW) 매칭

문제

링크: https://www.acmicpc.net/problem/10538
요약: o/x로 이루어진 작은 그림 hp×wp과 큰 걸작 hm×wm이 주어질 때, 작은 그림이 정확히 일치하는 시작 위치(좌상단)의 개수를 구합니다.
제한: 1 ≤ hp, wp, hm, wm ≤ 2000, 그리고 hm ≥ hp, wm ≥ wp.

입력/출력

1
2
3
4
5
6
7
<입력>
hp wp hm wm
hp줄: 사용한 그림
hm줄: 걸작 그림

<출력>
일치하는 위치의 개수

예시

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
입력
4 4 10 10
oxxo
xoox
xoox
oxxo
xxxxxxoxxo
oxxoooxoox
xooxxxxoox
xooxxxoxxo
oxxoxxxxxx
ooooxxxxxx
xxxoxxoxxo
oooxooxoox
oooxooxoox
xxxoxxoxxo

출력
4

접근 개요

핵심 아이디어: 2차원 롤링 해시(행→열 두 단계)로 모든 hp×wp 서브매트릭스의 해시를 O(1)씩 갱신하며 비교합니다. 충돌은 서로 다른 두 쌍의 64-bit 기반 베이스를 사용한 이중 해시로 확률을 충분히 낮춥니다.
매핑: 문자 'o'와 'x'를 서로 다른 정수 값으로 매핑해 해시를 구성합니다.
절차:
1. 각 행에서 길이 wp의 구간 해시를 슬라이딩으로 계산.
2. 위 결과를 세로로 길이 hp만큼 다시 롤링해 각 좌상단 (i,j)의 2D 해시를 얻음.
3. 패턴의 2D 해시와 이중 비교하여 일치 횟수 누적.

알고리즘 설계

행 해시(가로 롤링): 베이스 Bcol에 대해 rowHash[i][j] = hash(M[i][j..j+wp-1])를 전처리. 다음 열로 이동 시 맨 왼쪽 원소 제거·오른쪽 원소 추가로 O(1) 갱신.
열 해시(세로 롤링): 각 열 창 j마다 v[i] = hash(rowHash[i..i+hp-1][j])를 O(1)로 갱신.
패턴 해시: 동일한 방식으로 패턴 P의 2D 해시 pat 계산.
이중 해시: (BASE_ROW_A, BASE_COL_A)와 (BASE_ROW_B, BASE_COL_B) 두 체계로 각각 계산하여 충돌 확률을 낮춤.
값 매핑: 'o'→1, 'x'→2 같은 간단·비충돌 매핑.

정당성(스케치)

2D 다항 해시는 각 원소의 위치에 따른 가중 합으로 정의되어 전이 시 이전 상태에서 일관성 있게 갱신됩니다.
동일 위치의 동일한 문자가 전 구간에 일치할 때만 두 해시가 동시에 일치할 확률이 높으며, 서로 독립적인 두 해시를 사용하면 충돌 확률은 실사용에서 무시 가능 수준으로 떨어집니다.

복잡도

시간: O(hm × wm)
공간: O(hm × (wm − wp + 1)) (행 해시 보관), 추가적으로 상수 크기 보조 배열

구현 (C++)

  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
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

using u64 = unsigned long long;

static inline u64 cellValue(char ch) {
	return ch == 'o' ? 1ULL : 2ULL; // 'o'와 'x'를 서로 다른 값으로 매핑
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int hp, wp, hm, wm;
	if (!(cin >> hp >> wp >> hm >> wm)) return 0;

	vector<string> P(hp), M(hm);
	for (int i = 0; i < hp; ++i) cin >> P[i];
	for (int i = 0; i < hm; ++i) cin >> M[i];

	// 2D Rolling Hash with double 64-bit bases (wrap-around modulo 2^64)
	const u64 BASE_COL_A = 146527ULL;
	const u64 BASE_ROW_A = 19260817ULL;
	const u64 BASE_COL_B = 911382323ULL;
	const u64 BASE_ROW_B = 972663749ULL;

	// Precompute powers
	vector<u64> powColA(wm + 1, 1), powRowA(hm + 1, 1);
	vector<u64> powColB(wm + 1, 1), powRowB(hm + 1, 1);
	for (int i = 1; i <= wm; ++i) {
		powColA[i] = powColA[i - 1] * BASE_COL_A;
		powColB[i] = powColB[i - 1] * BASE_COL_B;
	}
	for (int i = 1; i <= hm; ++i) {
		powRowA[i] = powRowA[i - 1] * BASE_ROW_A;
		powRowB[i] = powRowB[i - 1] * BASE_ROW_B;
	}

	// Pattern hash
	u64 patRowA, patRowB;
	vector<u64> patRowsA(hp), patRowsB(hp);
	for (int r = 0; r < hp; ++r) {
		u64 hA = 0, hB = 0;
		for (int c = 0; c < wp; ++c) {
			u64 v = cellValue(P[r][c]);
			hA = hA * BASE_COL_A + v;
			hB = hB * BASE_COL_B + v;
		}
		patRowsA[r] = hA;
		patRowsB[r] = hB;
	}
	u64 patA = 0, patB = 0;
	for (int r = 0; r < hp; ++r) {
		patA = patA * BASE_ROW_A + patRowsA[r];
		patB = patB * BASE_ROW_B + patRowsB[r];
	}

	// Row-wise rolling hashes for the masterpiece (width = wp)
	const int W = wm - wp + 1;
	const int H = hm - hp + 1;
	vector<vector<u64>> rowA(hm, vector<u64>(max(0, W)));
	vector<vector<u64>> rowB(hm, vector<u64>(max(0, W)));

	if (W <= 0 || H <= 0) {
		cout << 0 << '\n';
		return 0;
	}

	for (int i = 0; i < hm; ++i) {
		u64 hA = 0, hB = 0;
		for (int c = 0; c < wp; ++c) {
			u64 v = cellValue(M[i][c]);
			hA = hA * BASE_COL_A + v;
			hB = hB * BASE_COL_B + v;
		}
		rowA[i][0] = hA;
		rowB[i][0] = hB;
		for (int j = 1; j < W; ++j) {
			u64 vOut = cellValue(M[i][j - 1]);
			u64 vIn = cellValue(M[i][j + wp - 1]);
			hA = hA * BASE_COL_A + vIn - powColA[wp] * vOut;
			hB = hB * BASE_COL_B + vIn - powColB[wp] * vOut;
			rowA[i][j] = hA;
			rowB[i][j] = hB;
		}
	}

	// Vertical rolling for each column window
	long long answer = 0;
	for (int j = 0; j < W; ++j) {
		u64 vA = 0, vB = 0;
		for (int i = 0; i < hp; ++i) {
			vA = vA * BASE_ROW_A + rowA[i][j];
			vB = vB * BASE_ROW_B + rowB[i][j];
		}
		if (vA == patA && vB == patB) ++answer;
		for (int i = 1; i < H; ++i) {
			u64 outA = rowA[i - 1][j], inA = rowA[i + hp - 1][j];
			u64 outB = rowB[i - 1][j], inB = rowB[i + hp - 1][j];
			vA = vA * BASE_ROW_A + inA - powRowA[hp] * outA;
			vB = vB * BASE_ROW_B + inB - powRowB[hp] * outB;
			if (vA == patA && vB == patB) ++answer;
		}
	}

	cout << answer << '\n';
	return 0;
}