14425 문자열 집합 (Trie) [Silver IV]

트라이 (Trie)

 

트라이 자료구조를 이용해서 빠르게 탐색하는 방식으로 구현하였음.

 

#include <iostream>

using namespace std;
static int N, M;

class Node
{
public:
	Node* childs[26];
	bool isLeaf = false;

	Node()
	{
		fill(childs, childs + 26, nullptr);
	}

	void insert(const char* key)
	{
		if (*key == 0) {
			isLeaf = true;
			return;
		}

		int nextID = *key - 'a';
		if (childs[nextID] == nullptr)
			childs[nextID] = new Node();

		childs[nextID]->insert(key + 1);
	}

	Node* find(const char* key)
	{
		if (*key == 0)
			return this;

		int nextID = *key - 'a';
	
		if (childs[nextID] == nullptr) 
			return nullptr;

		return childs[nextID]->find(key + 1); 
		
	}
};

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

	cin >> N >> M;
	Node* root = new Node();

	while (N--)
	{
		char text[501];
		cin >> text;
		root->insert(text);
	}

	int count = 0;

	while (M--)
	{
		char text[501];
		cin >> text;
		Node* node = root->find(text);
		if (node && node->isLeaf)
			count++;
			
		
	}
	cout << count << "\n";

}