[BOJ]14425 : 문자열 집합(c++)

[문제] : https://www.acmicpc.net/problem/14425

[풀이]

포인터를 사용하지 않고 고정 길이 배열로 구현한 트라이를 사용해 문제를 풀었다. 포인터를 사용해 구현하는 쪽이 메모리가 더 많이 사용되고 느리다고 해서 고정 길이 배열로 트라이 문제를 풀어보고 있다. 이 문제는 가장 기본적인 트라이 문제로 트리를 만드는 insert 부분과 문자열을 찾는 find 부분만 구현하면 문제가 해결된다. 고정 길이 배열로 트라이를 구현하는 경우 배열의 크기는 [트라이의 최대 글자갯수][트라이 노드마다 포인터갯수] 로 두면 된다.

[코드]

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>

using namespace std;

const int GO_MAX = 26;
const int CHA_MAX = 5000000;
vector<pair<int, string>> input;
struct Trie {
	int cnt;
	int go[CHA_MAX + 1][GO_MAX];
	bool output[CHA_MAX + 1];
	bool goexist[CHA_MAX + 1];

	Trie() {
		cnt = 1;
		memset(go, 0, sizeof go);
		memset(output, 0, sizeof output);
		memset(goexist, 0, sizeof goexist);
	}

	void insert(const char* key, int node=0) {
		if (*key == '\0')
		{
			output[node] = true;
			return;
		}

		int next = *key - 'a';
		if (!go[node][next]) go[node][next] = cnt++;
		goexist[node] = true;
		insert(key + 1, go[node][next]);
	}

	bool find(const char* key, int node = 0)
	{
		if (*key == '\0')
		{
			if (!output[node]) return false;
			return true;
		}

		int next = *key - 'a';
		if (!go[node][next])
		{
			return false;
		}

		return find(key + 1, go[node][next]);
	}

};

int main(void)
{
		int N, P;
		cin >> N >> P;

		bool result = true;
		Trie trie;

		for (int i = 0; i < N; ++i)
		{
			char tell[501];
			cin >> tell;
			trie.insert(tell);
		}
		int sum = 0;
		for (int i = 0; i < P; ++i)
		{
			char tell2[501];
			cin >> tell2;
			if (trie.find(tell2) == true)
			{
				sum++;
			}
		}

		cout << sum << endl;
	

	return 0;
}

지적 환영합니다