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

문제

14426번: 접두사 찾기

풀이

문자열, 트라이

[백준][C++] 5052: 전화번호 목록

위의 문제 처럼 트라이를 사용하는 문제다.

 

특정 문자열이 현재 트라이 자료구조 내의 문자열의 접두사인지 판별하는 과정은 다음과 같다. 

1. 트라이에서 하나의 노드는 입력되는 문자의 종류만큼의 자식 노드를 가진다. 
2. 특정 문자열의 가장 앞의 문자부터 진행한다. 
3. 현재 문자에 해당하는 자식 노드가 비어있는지 판별한다. 
4. 자식 노드가 비어있지 않다면 다음 문자를 판별한다. 
5. 자식 노드가 비어있다면 이전에 입력된 문자열 중에서 해당 자식 노드를 방문하지 않았다는 뜻이므로, 특정 문자열은 접두사가 아니다. 

코드

#include <iostream>

using namespace std;

const int MAX_NUM = 26;

struct Trie
{
	Trie()
		: isEnd(false)
	{
		for (int i = 0; i < MAX_NUM; ++i)
		{
			child[i] = NULL;
		}
	}

	~Trie()
	{
		for (int i = 0; i < MAX_NUM; ++i)
		{
			if (child[i] != NULL)
			{
				delete child[i];
			}
		}
	}

	void Insert(const char* str)
	{
		// 마지막 문자라면 isEnd를 true로 설정
		if (*str == NULL)
		{
			isEnd = true;
			return;
		}

		// 문자열의 첫 문자에 해당하는 자식 노드를 탐색
		int current = *str - 'a';
		if (child[current] == NULL)
		{
			child[current] = new Trie();
		}

		// 다음 문자를 인자로 자식 노드의 Insert 실행
		child[current]->Insert(str + 1);
	}

	bool Find(const char* str)
	{
		if (*str == NULL)
		{
			return false;
		}

		// 현재까지의 문자열이 들어온 적 있는 문자열인 경우
		if (isEnd == true)
		{
			return true;
		}

		int current = *str - 'a';
		if (child[current] == NULL)
		{
			return false;
		}

		return child[current]->Find(str + 1);
	}

	Trie* HasPrefix(const char* str)
	{
		if (*str == NULL)
		{
			return this;
		}

		int current = *str - 'a';
		if (child[current] == NULL)
		{
			return NULL;
		}

		return child[current]->HasPrefix(str + 1);
	}

	// Trie의 노드는 입력되는 문자의 종류만큼의 자식 노드를 가진다.
	Trie* child[MAX_NUM];
	bool isEnd;

};

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;

	Trie trie;

	for (int i = 0; i < N; ++i)
	{
		char s[501];
		cin >> s;

		trie.Insert(s);
	}

	int answer = 0;
	for (int i = 0; i < M; ++i)
	{
		char s[501];
		cin >> s;

		if (trie.HasPrefix(s) != NULL)
		{
			answer++;
		}
	}

	cout << answer;

	return 0;
}