글 읽기 - OutOfBound 질문입니다

pppp1923 1년 전 0

메모리풀 방식으로 노드를 저장했는데 5%에서 아웃오브바운드로 나오네요 ㅠㅠ

문자열 길이가 500이고 알파벳 개수만큼 가능성이 있으니깐 500 * 26 = 13000개이므로 pool배열의 크기를 20000으로 설정했는데 다른 문제가 무엇일까요? ㅠㅠ

#include <iostream>
using namespace std;

struct Node {
	Node* child[26];
	int is_finish;
	Node() {
		for (int i = 0; i < 26; i++) child[i] = nullptr;
		is_finish = 0;
	}
} pool[20000];
int pool_size;

struct Trie {
	Node root;

	void add(Node* node, char str[], int index) {
		if (str[index] == 0) {
			node->is_finish = 1;
			return;
		}
		int c = str[index] - 'a';
		if (node->child[c] == nullptr) {
			Node* new_node = &pool[pool_size++];
			node->child[c] = new_node;
		}
		add(node->child[c], str, index + 1);
	}
	
	void insert(char str[]) {
		add(&root, str, 0);
	}

	int find(Node* node, char str[], int index) {
		if (node == nullptr) return 0;
		if (str[index] == 0) return node->is_finish;
		int c = str[index] - 'a';
		return find(node->child[c], str, index + 1);
	}

	int search(char str[]) {
		return find(&root, str, 0);
	}
};


int n, m;

int main() {
	int ans = 0;
	Trie trie;
	cin >> n >> m;
	while (n--) {
		char str[501];
		cin >> str;
		trie.insert(str);
	}
	while (m--) {
		char str[501];
		cin >> str;
		if (trie.search(str)) ans++;
	}
	cout << ans << "\n";
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

OutOfBound 질문입니다

pppp1923 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말