BOJ - 문자열 집합(14425)

트라이나 문자열 맵을 이용해서 해결할 수 있는 문제입니다. 트라이를 연습하기 위해 풀었던 문제이기 때문에 트라이로 구현하였습니다. 입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있느 것이 몇 개인지 구하는 문제입니다. 만약 그룹의 문자열이 abcd라면 주어지는 문자열이 abc인 경우와 abcde인 겨우 모두 고려해야 합니다.

문자열이 abc인 경우에는 집합의 길이보다 짧기 때문에 트라이를 순회하고 마지막 노드에서 끝난 집합이 있는지 확인합니다. 그런데 문자열이 abcde인 경우 abcd까지 순회하고 끝나기 때문에 집합이 존재한다고 생각하게 됩니다. 그렇기 때문에 별도의 Flag를 둬서 주어진 문자열을 모두 탐색하지 못하고 순회가 종료되었다는 것을 별도로 표시해줘야 합니다.

즉, 트라이를 이용해서 같은 문자열(‘abcd’)이 있는지 확인할 때는 문자열 탐색을 모두 마쳤을 때(‘abc’)와 중간에 끝났을 때(‘abcde’)를 모두 고려해야 합니다.

풀이 코드

#include <iostream>
#include <stdio.h>

using namespace std;

int trie[5000000][27];
int trie_idx;

int trie_count[5000000];

int main() {

	int N, M;
	scanf("%d %d", &N, &M);

	int top = trie_idx++;
	int ans = 0;

	// add
	for (int i = 0; i < N + M; i++) {
		char str[501];
		cin >> str;

		// trie
		int cur = top;

		// 문자수가 집합 S에 속해있는 문자수보다 큰 경우를 체크
		// (이런경우 trie_count 로 확인할 수 없다.)
		int is_more = false;
		for (int j = 0; str[j] != 0; j++) {
			int c = str[j] - 'a';

			// 다음 노드가 없는 경우 생성
			if (trie[cur][c] == 0) {
				// 그룹생성을 위해 다음 노드 생성
				if (i < N) {
					trie[cur][c] = trie_idx++;

				// 그룹이 없는 경우
				} else {
					is_more = true;
					break;
				}
			}
			
			// 다음 노드로 이동
			cur = trie[cur][c];
		}

		// 등록
		if (i < N) {
			trie_count[cur]++;
			
		// 찾기
		} else {
			if (is_more == false && trie_count[cur] > 0) {
				ans++;
			}
		}
	}

	printf("%d", ans);

	return 0;
}