[c++] 백준 14425 문자열 집합

백준 단계별로 풀어보기 [문자열 알고리즘 1] 문자열 집합

https://www.acmicpc.net/problem/14425

14425번: 문자열 집합

 

[풀이]

트라이 알고리즘으로 insert와 find 함수를 구현하여 풀 수 있다. 트라이 알고리즘에 대한 공부는 알고리즘 카테고리에서...

 

[코드]

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

class Node {
	public:
		Node* childs[26] = { NULL };
		bool finish = false;

		Node() {}

		~Node() {
			for (int i = 0; i < 26; i++)
				if (childs[i])
					delete childs[i];
		}
};

class Trie {
	public:
		Node* root;
		Trie() { this->root = new Node(); }

		void insert(string& str) {
			Node* curr = this->root;

			for (int i = 0; i < str.length(); i++) {
				if (curr->childs[str[i] - 'a'] != NULL)
					curr = curr->childs[str[i] - 'a'];
				else {
					curr->childs[str[i] - 'a'] = new Node();
					curr = curr->childs[str[i] - 'a'];
				}
			}

			curr->finish = true;
		}

		bool find(string& str) {
			Node* curr = this->root;
			for (int i = 0; i < str.length(); i++) {
				if (curr->childs[str[i] - 'a'] == NULL)
					return 0;
				else
					curr = curr->childs[str[i] - 'a'];
			}

			if (curr->finish) return 1;
			else return 0;
		}
};


int main() {
	//trie 알고리즘
	Trie trie;
	int n, m;
	cin >> n >> m;
	string s;
	for (int i = 0; i < n; i++) {
		cin >> s;
		trie.insert(s);
	}

	int cnt = 0;
	for (int i = 0; i < m; i++) {
		cin >> s;
		int ans = trie.find(s);
		if (ans == 1)
			cnt++;
	}

	cout << cnt;

	return 0;
}