Trie란?
간단히 말해서 여러 문자열을 Tree에 한 글자씩 넣은 자료구조이다. Prefix Tree라고도 불리며
동일한 접두사를 갖는 문자열을 빠르게 찾을 수 있다.
- 알파벳 Trie의 뼈대는 다음과 같다.
struct Trie{
struct Node{
int child[26];
bool valid;
Node()
{
for(int i=0;i<26;i++)
{
child[i]=-1;
}
valid = false;
}
};
vector<Node> trie;
int root;
};
- 다음으로 자식을 만드는 함수가 필요하다.
int product()
{
Node next;
trie.push_back(next);
return (int)trie.size() - 1; // size()는 unsigned integer를 반환하므로 int로 형변환해주는 습관을 갖자!
}
- 이제 Trie의 핵심인 add와 search함수를 구현해보자.
void add(string &str, int node, int index)
{
if(index==str.length())
{
trie[node].vaild = true;
return;
}
int c = str[index]-'a';
if(trie[node].child[c]==-1) // trie에 없는 문자열이면 새로운 node를 만들어주자!
{
int new_node = product();
trie[node].child[c] = new_node;
}
int next = trie[node].child[c];
add(str,next,index+1);
}
void add(string &str)
{
add(str, root, 0);
}
bool search(string &str, int node, int index)
{
if(node==-1)
{
return false;
}
if(index==str.length())
{
return trie[node].vaild;
}
int c = str[index]-'a';
int next = trie[node].child[c];
return search(str, next, index+1);
}
bool search(string &str)
{
return search(str, root, 0);
}