글 읽기 - c++double free or corruption (out) 관련 질문드립니다!

huh0918 1년 전 0

아래와 같이 트라이 구현했습니다. 다만 예제도 통과를 못하고, 몇가지 케이스 만들어서 시도를 해보면 위 오류가 발생합니다. 개인적으로 디폴트 destructor가 잘 작동할 거라 생각했는데, 놓친 부분이 있을까요?

어느 부분에서 오류가 발생했는는지, 그리고 로직이 어디가 틀린건지 지적해주시면 정말 감사하겠습니다!

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

class Node {
	public : 
	int child[26]; // 자식의 인덱스(주소) (-1 : 없음, 0이상 : 있음)
	bool valid; // true면 최종 값 ,false면 지나가는 값
	
	Node() {
		memset(child, -1, sizeof(child));
		valid = false;
	}
};

class Trie {
	private:
	vector<Node> trie;
	int root;
	
	int Init() {
		trie.push_back(Node ());
		return (int)trie.size() - 1;
	} // Node생성후 해당 주소(인덱스) 리턴
	
	void add_hidden(int node_idx, const string &s, int str_idx) {
		if(str_idx == s.size()) {
			trie[node_idx].valid = true;
			return;
		}
		
		int child_idx = s[str_idx] - 'a';
		int child_node_idx = trie[node_idx].child[child_idx];
		if (child_node_idx == -1) { // 노드없어서 만들어야됨
			// 노드생성
			trie[node_idx].child[child_idx] = Init();
			child_node_idx = trie[node_idx].child[child_idx];
		}
		
		add_hidden(child_node_idx, s, str_idx+1);
	}
	
	bool search_hidden(int node_idx, const string &s, int str_idx) {
		if (node_idx == -1) return false;
		if (str_idx == s.size())
			return trie[node_idx].valid;
		
		int child_idx = s[str_idx] - 'a';
		int child_node_idx = trie[node_idx].child[child_idx];
		return search_hidden(child_node_idx, s, str_idx+1);		
	}
	
	
	public :

	// Constructor
	Trie() {
		trie.push_back( Node ());
		root = (int)trie.size()-1;
	}
	// add
	void add( const string &s ) {
		if (s.size() == 0) return;
		add_hidden( root, s,  0);
	}
	// search
	bool search( const string &s ) {
		if (s.size() == 0) return false;
		return search_hidden(root, s, 0);
	}
	
};


int main() {
	//cin.tie(nullptr); ios_base::sync_with_stdio(false);
	int n ,m;
	cin >> n >> m;
	
	Trie s;
	for (int i=0; i<n; ++i) {
		string temp;
		cin >> temp;
		s.add(temp);
	}
	
	cout << '\n';
	int ans = 0;
	for (int i=0; i<m; ++i) {
		string temp;
		cin >> temp;
		cout <<temp << " : " << s.search(temp) << endl;
		if ( s.search(temp) )
			ans++;
	}	

	cout << ans << endl;
}

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

문제

문제

출처

ICPC

c++double free or corruption (out) 관련 질문드립니다!

huh0918 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말