TRIE 자료구조를 사용한 문자열 검색

반응형

Trie 자료구조란?

다음과 같이 여러 문자열 사전을 저장하는 트리 형태의 자료구조 이다.

Trie에 텍스트 T의 모든 접미사를 저장한다고 하면 O(M)만에 패턴 P를 찾을 수 있다.

다음은 Trie 구조에 전화 번호 목록을 저장해 탐색해가며 일관성 여부를 출력하는 문제와 코드이다.

 

# BOJ 5052:전화번호 목록

 

#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;
 
typedef struct NODE {
    struct NODE* next[10];
    int end;
    NODE() :next(), end(0) {};
}Node;
 
Node* makeNewNode() {
    Node* newNode = (Node*)malloc(sizeof(Node));
    for (int i = 0; i < 10; i++) {
        newNode->next[i] = NULL;
    }
    newNode->end = 0;
    return newNode;
}
void deleteNode(Node* root) {
    Node* pre = root;
    for (int i = 0; i < 10; i++) {
        if (pre->next[i]) {
            deleteNode(pre->next[i]);
        }
    }
    delete pre;
    return;
}
bool insertNode(Node **root, char* str) {
    int len = strlen(str);
    Node* cur = *root;
    for (int i = 0; i < len; i++) {
        if (!cur->next[str[i]-'0']) {    //현재의 다음노드가 비어있을 경우
            if (cur->end) {    //끝일 경우
                return false;
            }
            cur->next[str[i] - '0'] = makeNewNode();
        }
        cur = cur->next[str[i] - '0'];
    }
    cur->end = 1;
    for (int i = 0; i < 10; i++) {
        if (cur->next[i])    return false;
    }
    return true;
}
int main() {
    int T, N;
    register int t, i, j;
 
    cin.clear();
    cin >> T;
    for (t = 1; t <= T; t++) {
        cin >> N;
        char str[10005][11];
        for (i = 0; i < N; i++)
            cin >> str[i];
        bool check = true;
        Node* root = makeNewNode();    //노드 생성
        for (i = 0; i< N; i++) {
            check = insertNode(&root, str[i]);
            if (!check)
                break;
        }
        if (check)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
        deleteNode(root);
    }
    return 0;
}