[BOJ] 10538 빅 픽쳐 - 라이브러리 사용 x (문자열 map 구현, 큐 구현)

문제: https://www.acmicpc.net/problem/10538

 

 

문제 풀이:

 

* 이 분의 풀이를 참고하여 풀었습니다.

 

작은 그림의 높이: q, 너비: w

큰 그림의 높이: e, 너비: r

 

Part 1. 작은 그림

작은 그림의 행을 하나의 단어로 취급

즉 작은 그림은 q개의 단어를 가짐

 

각 단어를 map에 넣어 번호를 매긴다 -> 중복되면 같은 번호를 가지는 것

 

이때 저는 map을 구현하여 값이 저장된 위치를 단어의 번호로 사용하였습니다.

 

map에 존재하지 않는 단어이다 -> trie에 insert  -> trie 속 단어의 끝에 해당 단어의 번호를 저장해준다. (terminal=num)

 

* map에 이미 존재하는 단어를 넣어봐야 중복되서 의미 없음

 

 

Part 2. 큰 그림

큰 그림의 한 줄씩 보면서, 그 행에 작은 그림의 단어(한 줄)가 포함되는지 찾는다. 작은 그림의 단어가 존재한다면 그 위치에 그 단어의 번호를 저장해놓는다 (check[i][j]=num)

 

 

Part 3.

이렇게 작은 그림과 겹치는 부분만 표시해둔 check[i][j]에서 작은 그림에서 단어 번호의 나열과 같은 것을 찾는다.

즉, 

check 배열은 다음과 같이 된다.

 

 

 

 

-> 크기: e X r  

-> 빨간색으로 표시한 단어의 번호 외에는 모두 -1

-> 네 번째 세로 값은 다음과 같다 (-1,1,2,2,1,-1,-1,-1,-1,-1)

 

 

 

 

 

 

 

 

이렇게 세로로 문자열을 보면서 작은 그림의 (1221)과 같은 문자열이 포함되어 있는 것이 몇 개인지 카운팅한다.

 

 

소스 코드:

#include <iostream>
#define HASHMAX 100019
#define QSIZE 4002
#define a 17
#define b 7
using namespace std;

int q, w, e, r,hashtable[HASHMAX];
int check[2002][2002],m1_num[2002],pi[2002];
char m1[2002][2002], m2[2002][2002];


int _strlen(char str[]) {
	int i = 0;
	while (str[i] != '\0') i++;

	return i;
}
int convert(char str[]) {
	int ret = 401;
	int len = _strlen(str);
	for (int i = 0; i < len; i++) {
		ret = ((ret << 4) + (int)(str[i])) % HASHMAX;
	}
	return ret % HASHMAX;
}
int insert(char str[]) {
	int key = convert(str);
	int p = (a*key - b) % HASHMAX;
	while (hashtable[p] != -1) {
		p = (p + 1) % HASHMAX;
	}
	hashtable[p] = key;
	return p;
}
int find(char str[]) {
	int key = convert(str);
	int p = (a*key - b) % HASHMAX;
	while (hashtable[p] != key) {
		if (hashtable[p] == -1) return -1;
		p = (p + 1) % HASHMAX;
	}
	return p;
}

struct trie {
	trie *next[2];
	trie *fail;
	int terminal;

	trie() {
		next[0] = next[1] = nullptr;
		terminal = -1;
	}
	~trie() {
		if (next[0]) delete next[0];
		if (next[1]) delete next[1];
	}
	void insert(const char* word, int num) {
		if (*word == '\0') {
			terminal = num;
			return;
		}
		int n;
		if (*word == 'o') n = 0;
		else n = 1;
		if (!next[n]) next[n] = new trie;
		
		next[n]->insert(word+ 1, num);
	}
};
trie *qq[QSIZE];

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

	
	cin >> q >> w >> e >> r;

	for (int i = 0; i < HASHMAX; i++) hashtable[i] = -1;
	
	trie *root = new trie;
	for (int i = 0; i < q; i++) {
		cin >> m1[i];

		if (find(m1[i])== -1) {
			int t=insert(m1[i]);
			m1_num[i] = t ;
			root->insert(m1[i], t);
			
		}
		else m1_num[i] = find(m1[i]);
	}
	for (int i = 0; i < e; i++) cin >> m2[i];


	// fail 함수 만들기
	root->fail = root;
	qq[0]=root;
	int front = 0;
	int top = 1;
	while (top!=front) {
		trie *cur = qq[front];
		front = (front + 1) % QSIZE;

		for (int i = 0; i < 2; i++) {
			trie *next = cur->next[i];
			if (!next) continue;

			if (cur == root) next->fail = root;
			else {
				trie *dest = cur->fail;

				while (dest != root && !dest->next[i]) dest = dest->fail;

				if (dest->next[i]) dest = dest->next[i];

				next->fail = dest;
			}
			if (next->fail->terminal!=-1) next->terminal = next->fail->terminal;

			qq[top] = next;
			top = (top + 1) % QSIZE;
		}
	}

	
	for (int i = 0; i < e; i++) {
		trie *cur = root;
		for (int j = 0; j < r; j++) {
			int next;
			if (m2[i][j] == 'o') next = 0;
			else next = 1;
			while (cur != root && !cur->next[next]) cur = cur->fail;
			if (cur->next[next]) cur = cur->next[next];
			if (cur->terminal!=-1) check[i][j] = cur->terminal;
			else check[i][j] = -1;
		}
	}


	//pi 값 테이블 작성
	for (int i = 1, j = 0; i < q; i++) {
		while (j > 0 && m1_num[i] != m1_num[j]) j = pi[j - 1];
		if (m1_num[i] == m1_num[j]) pi[i] = ++j;
	}

	int res = 0;
	for (int j = 0; j < r; j++) {
		int w = 0;
		for (int i = 0; i < e; i++) {
			while (w > 0 && check[i][j] !=	m1_num[w]) w = pi[w - 1];
			if (check[i][j] == m1_num[w]) {
				if (w == q - 1) {
					res++;
					w = pi[w];
				}
				else w++;
			}
		}
	}
	cout << res << '\n';
	return 0;
}