[백준 9250][💚2] 문자열 집합 판별 (아호-코라식, 트라이)

🚀 난이도

💚 플래티넘 2

🚀 문제

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

🚀 내 풀이

🔥 ‘아호-코라식’ 으로 풀이 ⭕

아호-코라식 알고리즘에 대해서는 (C++) 문자열 검색 알고리즘 : 아호-코라식(Aho-Corasick) 알고리즘 👈 이 포스트에 자세히 설명해두었으니 참고 :) 제출했던 아래 코드는 아호-코라식 코드 그대로이다.

아호 코라식 알고리즘을 사용하면, 검색어의 개수가 \(k\) 개 일 때 하나의 텍스트 당 \(O(n + m_{1} + m_{2} + .. + m_{k})\) 의 선형 시간 복잡도만 소요 된다. 즉, 텍스트(아래 코드에선 word[i])를 한번만 순회하면 되는 것이다.

#include <bits/stdc++.h>

using namespace std;

struct Trie {
public:
	bool isEnd;
	map<char, Trie*> child;
	Trie* fail;

	Trie() : isEnd(false), fail(nullptr) {}

	void Insert(string pattern) {
		Trie* now = this;
		int m = pattern.length();
		for (int i = 0; i < m; ++i) {
			if (now->child.find(pattern[i]) == now->child.end())
				now->child[pattern[i]] = new Trie;
			now = now->child[pattern[i]];

			if (i == m - 1) now->isEnd = true;
		}
	}

	void Fail() {  // BFS + KMP
		Trie* root = this;
		queue<Trie*> q;

		q.push(root);

		while (!q.empty()) {
			Trie* now = q.front();
			q.pop();

			for (auto& ch : now->child) {

				Trie* next = ch.second;
				if (now == root)
					next->fail = root;
				else {
					Trie* prev = now->fail;
					while (prev != root && prev->child.find(ch.first) == prev->child.end())
						prev = prev->fail;
					if (prev->child.find(ch.first) != prev->child.end())
						prev = prev->child[ch.first];
					next->fail = prev;
				}

				if (next->fail->isEnd)
					next->isEnd = true;

				q.push(next);
			}
		}
	}
};

// 검색어들이 모여 있는 트라이를 통해 탐색하며 word 의 부분 문자열과 일치하는 것을 처음으로 찾아내자마자 return true 하고 종료함
bool KMP(string word, Trie* root) {
	Trie* now = root;
	int n = word.length();
	for (int i = 0; i < n; ++i) {
		while (now != root && now->child.find(word[i]) == now->child.end())
			now = now->fail;
		if (now->child.find(word[i]) != now->child.end())
			now = now->child[word[i]];
		if (now->isEnd)
			return true;
	}
	return false;
}

int main() {
	//freopen("input.txt", "r", stdin);

	int N;
	cin >> N;
	vector<string> patterns(N);
	for (int i = 0; i < N; ++i)
		cin >> patterns[i];
	Trie* root = new Trie;
	for (int i = 0; i < N; ++i)
		root->Insert(patterns[i]);
	root->Fail();

	int Q;
	cin >> Q;
	vector<string> words(Q);
	for (int i = 0; i < Q; ++i)
		cin >> words[i];
	for (int i = 0; i < Q; ++i) {
		if (KMP(words[i], root))
			cout << "YES" << '\n';
		else
			cout << "NO" << '\n';
	}
}

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기