[BOJ] 9250 문자열 집합 판별

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

 

Ries님의 블로그와 위키백과를 통해 공부하였습니다. <- 전체 코드 및 설명 참고

 

 

코드 분석:

step 1. trie 만들기

struct trie {
	trie *next[26];
	trie *fail;
	bool finish;

	trie() {
		fill(next, next + 26, nullptr);
		finish = false;
	}
	~trie() {
		for (int i = 0; i < 26; i++) {
			if (next[i]) delete next[i];
		}
	}
	void insert(const char* key) {
		if (*key == '\0') {
			finish = true;
			return;
		}
		int word = *key - 'a';
		if (!next[word]) next[word] = new trie();
		next[word]->insert(key + 1);
	}
};

 

step 2. fail 함수 만들기 (BFS)

규칙 1. 루트에서 거리가 1인 것들(즉, root->next[i])의 fail은 root로 초기화한다.

규칙 2. 루트로부터 거리가 2 이상이면, 직전 노드의 fail을 따라가면서 자신과 같은 값을 만나면 그 노드를 fail로 설정

queue<trie*> q;
	root->fail = root;
	q.push(root);
	while (!q.empty()) {
		trie* cur = q.front();
		q.pop();

		for (int i = 0; i < 26; i++) {
			trie *next = cur->next[i];
			if (!next) continue;

			if (cur == root) next->fail = root;
			else {
            	// dest: 현재 노드의 fail
				trie *dest = cur->fail;
				
				//fail을 참조할 가장 가까운 조상을 찾아간다
                //현재 자신의 값(문자)가 i이므로 dest->next[i]==true라는 뜻은 dest의 문자가 현재 문자와 같다는 뜻
				while (dest != root && !dest->next[i]) {
					dest = dest->fail;
				}
				//fail(px)=go(fail(p),x)
				if (dest->next[i]) dest = dest->next[i];
				next->fail = dest;
			}
            
            // 현재 이전의 문자에서 문자열이 끝났다면, 현재 문자도 끝난 것
			if (next->fail->finish) next->finish = true;

			q.push(next);
		}
	}

 

step3. 입력 받은 문자열이 trie에 속하는지 찾기

cin >> str;
trie* cur = root;
bool res = false;
for (int c = 0; str[c]; c++) {
    int next = str[c] - 'a';

    //현재 경로로는 갈 수 없으면 fail을 계속 따라감
    while (cur != root && !cur->next[next]) {
    	cur = cur->fail;
    }
    // next 함수가 존재하면 이동. 루트면 이게 false일 수도 있다.
    if (cur->next[next]) cur = cur->next[next];

    //현재 노드에 finish가 있으면 찾은 것이다.
    if (cur->finish) {
    	res = true;
    	break;
    }
}

 

 

라이브러리 사용x

소스코드:

#include <iostream>
#define QSIZE 200002
using namespace std;


int n, m, pi[102];
struct trie {
	trie *next[26];
	trie *fail;
	bool finish;

	trie() {
		for (int i = 0; i < 26; i++) {
			next[i] = nullptr;
		}
		finish = false;
	}
	~trie() {
		for (int i = 0; i < 26; i++) {
			if (next[i]) delete next[i];
		}
	}
	void insert(const char *key) {
		if (*key == '\0') {
			finish = true;
			return;
		}
		int word = *key - 'a';
		if (!next[word]) next[word] = new trie;

		next[word]->insert(key + 1);
	}
};
trie *q[QSIZE];

void failfunc(trie *root) {
	q[0] = root;
	int front = 0;
	int top = 1;

	while (front != top) {
		trie *cur = q[front];
		front = (front + 1) % QSIZE;

		for (int i = 0; i < 26; i++) {
			trie *next = cur->next[i];
			if (!next) continue;

			if (cur == root) next->fail = root;
			else {
				trie *dest = cur->fail;
				while (dest != root && !dest->next[i]) dest = dest->fail;

				if (dest->next[i]) dest = dest->next[i];
				next->fail = dest;
			}
			if (next->fail->finish) next->finish = true;
			q[top] = next;
			top = (top + 1) % QSIZE;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	trie *root = new trie;
	for (int i = 0; i < n; i++) {
		char c[102];
		cin >> c;
		root->insert(c);
	}
	failfunc(root);
	cin >> m;
	for (int i = 0; i < m; i++) {
		char c[10002];
		cin >> c;

		int p = 0;
		trie *cur = root;
		bool res = false;
		while (c[p] != '\0') {
			int word = c[p] - 'a';
			while (!cur->next[word] && cur != root) cur = cur->fail;
			if (cur->next[word]) cur = cur->next[word];

			if (cur->finish) {
				res = true;
				break;
			}
			p++;
		}
		if (res) cout << "YES\n";
		else cout << "NO\n";
	}


	return 0;
}