[C++] 백준 14426번: 접두사 찾기

문제 링크

14426번: 접두사 찾기

문제 요약

N개의 문자열이 주어지고 M개의 문자열이 주어진다. M개의 문자열 중에서 집합 S에 포함되어 있는 문자열 중 적어도 하나의 접두사인 것의 개수를 구해야 한다.

접근 방법

쉬운 풀이가 있지만, 트라이 연습삼아서 트라이로 접근해봤습니다. N개의 문자열을 모두 트라이에 집어 넣은 뒤에, M개의 문자열에 대해 트라이에서 접근해봅니다. 접근 과정에서 NULL인 노드를 만나면 false를 리턴하고, 트라이에서 문자열의 끝까지 도달할 수 있다면 true를 리턴합니다. 이때, true인 문자열의 수를 출력하면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

struct Trie {
	Trie* node[26];

	Trie() {
		for (int i = 0; i < 26; i++) node[i] = NULL;
	}

	void insert(string& str, int idx) {
		if (idx == str.size())
			return;

		if (node[str[idx] - 'a'] == NULL)
			node[str[idx] - 'a'] = new Trie();
			
		node[str[idx] - 'a']->insert(str, idx + 1);
	}

	bool find(string& str, int idx) {
		if (idx == str.size())
			return true;

		if (node[str[idx] - 'a'] == NULL)
			return false;

		return node[str[idx] - 'a']->find(str, idx + 1);
	}

	void clear(void) {
		for (int i = 0; i < 26; i++) {
			if (node[i] != NULL) {
				node[i]->clear();
				delete node[i];
			}
		}
	}
};

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

	int n, m;
	cin >> n >> m;

	Trie* root = new Trie();

	for (int i = 0; i < n; i++) {
		string str;
		cin >> str;
		root->insert(str, 0);
	}

	int ans = 0;
	for (int i = 0; i < m; i++) {
		string str;
		cin >> str;
		
		if (root->find(str, 0))
			ans++;
	}

	cout << ans << '\n';
	root->clear();
	delete root;
	return 0;
}