문자열 매칭 알고리즘[3](트라이 & 아호 코라식)[String Searching Algorithm, Trie & Aho-Corasick]

KMP : 문자열 S가 있을 때, 패턴 P를 찾는 알고리즘

Trie : 문자열 N개가 있을 때, 문자열 S를 찾는 알고리즘
ex) 출석부에서 내 이름(full name) 찾기

Aho-corasick : 문자열 N개가 있을 때, 패턴 P를 찾는 알고리즘
ex)출석부에서 나랑 성이 같은 사람, 이름이 같은 사람을 찾기

 

코딩테스트 비중은 KMP보다 Trie가 더 높으며 Trie는 해시로 대처 할 수 있다고 함.

아호 코라식은 자주 나오는 문제는 아니다.

 

---

Trie 

 

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%9D%BC%EC%9D%B4_(%EC%BB%B4%ED%93%A8%ED%8C%85)

트라이 (컴퓨팅) - 위키백과, 우리 모두의 백과사전

 

숫자 비교는 O(1)이지만
문자열 비교는 최대 O(길이)가 걸린다.

문자열 N개를 담고있는 BST에서 검색하는데 걸리는 시간은 O(lgN)이 아니고 O(길이*lgN)이다.
N개 문자열을 오름차순 정렬(길이의 최댓값 M) : NMlgN

트라이의 한 노드는 어떤 문자열의 접두사를 나타낸다.
따라서, Trie는 prefix Tree라고도 한다.

트라이의 초기 상태 : 루트("")만 있다.


트라이는 우리가 추가 하지 않은 문자열도 트리에 추가 되어 있다.
고로 우리가 추가한 문자열만 valid 변수를 통해서 구별한다.

모든 노드의 level, 높이는 문자열의 길이와 같다.

 

//트라이 대신 해시로 풀 수 있는 문제가 많다 하하

구현

#include <string>
#include <vector>
using namespace std;

struct Trie {
	struct Node {
		int children[26];						// 알파벳 소문자 26개
		bool valid;								// true : 추가한 문자열
		Node() {
			for (int i = 0; i < 26; ++i) {
				children[i] = -1;
			}
			valid = false;
		}
	};

	vector<Node> trie;
	int root;

	int init() {
		Node x;
		trie.push_back(x);
		return (int)trie.size() - 1;
	}
	Trie() {
		root = init();
	}
	void add(int node, string &s, int index) {	//node : 탐색하고 있는 노드의 인덱스, s :  추가하고 있는 문자열, 
		if (index == s.size()) {
			trie[node].valid = true;
			return;
		}
		int c = s[index] - 'a';					// 자식의 인덱스
		if (trie[node].children[c] == -1) {		// 없다면
			int next = init();
			trie[node].children[c] = next;
		}
		int child = trie[node].children[c];
		add(child, s, index + 1);
	}
	void add(string &s) {
		add(root, s, 0);
	}

	bool search(int node, string &s, int index) {
		if (node == -1) return false;
		if (index == s.length())
			return true;
			//return trie[node].valid;
		int c = s[index] - 'a';
		int child = trie[node].children[c];
		return search(child, s, index + 1);
	}
	bool search(string &s) {
		return search(root, s, 0);
	}
};

vaild로 추가한 문자열과 중간 과정때문에 생긴 노드와 구별.

 

 

 

Aho-corasick

 

Aho-corasick : 문자열 N개가 있을 때, 패턴 P를 찾는 알고리즘

ex)출석부에서 나랑 성이 같은 사람, 이름이 같은 사람을 찾기

kmp에서의 fail을 trie에서도 구현하는 것
fail[i] s의 i까지 부분 문자열(접두사)에서 prefix == suffix 중에서 가장 긴 문자열의 길이
->
fail[node] = node가 나타내는 문자열s의 suffix이면서 trie에 포함된 가장 긴 문자열

https://ko.wikipedia.org/wiki/%EC%95%84%ED%98%B8_%EC%BD%94%EB%9D%BC%EC%8B%9D_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

아호 코라식 알고리즘 - 위키백과, 우리 모두의 백과사전

//Aho-Corasick
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>

using namespace std;
struct nd {
	int child[26];
	int pi;
	bool valid;
	nd() {
		for (int i = 0; i<26; i++) {
			child[i] = -1;
		}
		valid = false;
		pi = -1;
	}
};
vector<nd> tr;
int init() {
	nd x;
	tr.push_back(x);
	return (int)tr.size() - 1;
}
void add(int nd, string &s, int index) {
	if (index == s.size()) {
		tr[nd].valid = true;
		return;
	}
	int c = s[index] - 'a';
	if (tr[nd].child[c] == -1) {
		int next = init();
		tr[nd].child[c] = next;
	}
	add(tr[nd].child[c], s, index + 1);
}
int main() {
	int root = init();
	int n;
	cin >> n;
	vector<string> a(n);
	for (int i = 0; i<n; i++) {
		cin >> a[i];
		add(root, a[i], 0);
	}										// ↑ trie 코드, 
	queue<int> q;							// fail 값 찾기.
	tr[root].pi = root;
	q.push(root);
	while (!q.empty()) {					//bfs로 fail 값 찾기, prefix ==suffix, 길이 < 문자열
		int cur = q.front();
		q.pop();
		for (int i = 0; i<26; i++) {
			int next = tr[cur].child[i];
			if (next == -1) continue;
			if (cur == root) {
				tr[next].pi = root;			// 길이가 1인 prefix
			}
			else {							// kmp와 같은 과정 ~
				int x = tr[cur].pi;
				while (x != root && tr[x].child[i] == -1) {
					x = tr[x].pi;
				}
				if (tr[x].child[i] != -1) {
					x = tr[x].child[i];
				}
				tr[next].pi = x;		
			}								// ~ kmp와 같은 과정
			int pi = tr[next].pi;
			tr[next].valid |= tr[pi].valid;	//문자열이 or 연산으로 위도 찾았다고 할때
			q.push(next);
		}
	} // ~fail 값 계산 완료.
	int m;
	cin >> m;
	while (m--) {
		string s;
		cin >> s;
		int nd = root;
		bool ans = false;
		for (int i = 0; i<s.size(); i++) {	//kmp와 같은 과정 ~
			int c = s[i] - 'a';
			while (nd != root && tr[nd].child[c] == -1) {
				nd = tr[nd].pi;
			}
			if (tr[nd].child[c] != -1) {
				nd = tr[nd].child[c];
			}
			if (tr[nd].valid) {
				ans = true;
			}
		}									// ~ kmp와 같은 과정
		cout << (ans ? "YES" : "NO") << '\n';
	}
	return 0;
}

 

백준관련문제

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

14426번: 접두사 찾기

내 제출코드 : http://boj.kr/74a8b3ea4b824688bc86917415ea9f6b

 

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

9250번: 문자열 집합 판별

내 제출코드 : http://boj.kr/b189c62c8d284b96a852f52a4d44f894