트라이

1. 개념

---

문자열을 효율적으로 처리하기 위한 트리 자료구조

• 삽입 삭제 탐색에 있어서 O(|S|) 시간이 소요
• 그러나 메모리는 최대 4*글자의 종류 만큼 차지하므로 메모리 효율은 좋지 않다.
• 이론적인 시간 복잡도와 달리 실제로는 트라이가 해시나 이진 검색 트리에 비해 느리다.
  • 그러나 이 특징을 사용해야하는 문제가 있다.
  • 문자열의 접두사 검색 등과 같은 느낌

 

 

2. 구현

---

코드

#include <iostream>
using namespace std;

const int ROOT = 1;
int unused = 2; //새로 추가할 정점
const int MX = 10000 * 500 + 5; //최대 등장 가능한 글자 수 -> 최대 500인 문자열이 10000개 들어온 경우
bool chk[MX];
int nxt[MX][26]; // 각 정점에서 자식 정점의 번호 (가능한 문자가 소문자인 경우)

int c2i(char c)
{
	return c - 'A';
}

void insert(string& s)
{
	int cur = ROOT;
	for (auto c : s)
	{
		if (nxt[cur][c2i(c)] == -1)
			nxt[cur][c2i(c)] = unused++;
		cur = nxt[cur][c2i(c)];
	}
	chk[cur] = true;
}

bool find(string& s)
{
	int cur = ROOT;
	for (auto c : s)
	{
		if (nxt[cur][c2i(c)] == -1)
			return false;
		cur = nxt[cur][c2i(c)];
	}
	return chk[cur];
}

void erase(string& s)
{
	int cur = ROOT;
	for (auto c : s)
	{
		if (nxt[cur][c2i(c)] == -1)
			return;
		cur = nxt[cur][c2i(c)];
	}
	chk[cur] = false;
}

int main()
{
	for (int i = 0; i < MX; ++i)
		fill(nxt[i], nxt[i] + 26, -1);

	///
}

 

 

3. 문제

---

boj 14426

 

 

참고)

https://blog.encrypted.gg/1059

[실전 알고리즘] 0x1F강 - 트라이