![[_2021-01-19__10.25.07.png]]

const int alphabet = 26;
inline int ctoi(char c) { return (c >= 'a') ? c - 'a' : c - 'A'; }
class Trie {
public:
    bool terminal;
    Trie *child[alphabet];

    Trie() : terminal(false) {
        memset(child, 0, sizeof child);
    }
    ~Trie() {
        for (int i = 0; i < alphabet; i++) {
            delete child[i];
        }
    }
    void insert(const char* key) {
        if(*key == 0) terminal = true;
        else {
            int next = ctoi(*key);
            if (!child[next]) child[next] = new Trie();
            child[next]->insert(key + 1);
        }
    }
    Trie *find(const char *key) {
        if(*key == 0) return this;
        int next = ctoi(*key);
        if(!child[next]) return nullptr;
        return child[next]->find(key + 1);
    }
};

// map을 이용한 trie
class Trie {
public:
    bool terminal;
    unordered_map<char, Trie*> child;
    
    Trie() : terminal(false) {}
    void insert(const char* key) {
        if(*key == 0) terminal = true;
        else {
            if (!child[*key]) child[*key] = new Trie();
            child[*key]->insert(key + 1);
        }
    }
    Trie *find(const char *key) {
        if(*key == 0) return this;
        if(!child[*key]) return nullptr;
        return child[*key]->find(key + 1);
    }
};

공간복잡도

(포인터 크기) x (포인터 배열 개수) x (총 노드 개수)가 된다.
포인터 크기 = 8 byte,
포인터 배열 개수 = 26개,
1000길이의 문자열 1000개가 들어오면 10^6개의 총 노드가 필요하다.

즉, 8 x 26 x 10^6 = 약 200MB가 된다.

아호-코라식(Aho-Corasick) 알고리즘

KMP + Trie를 이용한 알고리즘이다.
일대다 문자열 탐색 알고리즘

길이 n의 text에 대해 m1~mk의 string이 부분문자열이 되는지 확인
O(n + m1 + m2 + … +mk) 의 시간복잡도

fail 링크를 연결해 해당 단어에서 틀려도 pi함수가 반환하는 곳으로(접미사 접두가 최대 일치 길이) 돌아간다.

class Trie {
public:
    bool terminal;
    Trie *fail;
    unordered_map<char, Trie*> children;

    Trie() : terminal(false) {}

    void insert(const char* key) {
        if(*key == 0) terminal = true;
        else {
            if (!children[*key]) children[*key] = new Trie();
            children[*key]->insert(key + 1);
        }
    }
    void linkFail() {
        Trie *root = this;
        queue<Trie*> q;
        q.push(root);
        while(!q.empty()) {
            Trie *here = q.front(); q.pop();
            for(auto &child : here->children) {
                Trie *there = child.second;
                if(here == root) there->fail = root;
                else {
                    Trie *prev = here->fail;
                    while(prev != root && prev->children.find(child.first) == prev->children.end()) prev = prev->fail;
                    if(prev->children.find(child.first) != prev->children.end()) prev = prev->children[child.first];
                    there->fail = prev;
                }
                if(there->fail->terminal) there->terminal = true;
                q.push(there);
            }
        }
    }
};

// find substring of text in root
bool kmp(Trie *root, string text) {
    Trie *here = root;
    for(char c : text) {
        while(here != root && here->children.find(c) == here->children.end()) here = here->fail;
        if(here->children.find(c) != here->children.end()) here = here->children[c];
        if(here->terminal) return true;
    }
    return false;
}

어려웠던 문제

[!info] 9202번: Boggle
상근이는 보드 게임 "Boggle"을 엄청나게 좋아한다.
https://www.acmicpc.net/problem/9202

[!info] 13505번: 두 수 XOR

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

[!info] 3172번: 현주와 윤주의 재미있는 단어 게임
현주와 윤주는 일요일마다 재미있는 단어 게임을 하면서 시간을 보낸다.
https://www.acmicpc.net/problem/3172

[!info] 16902번: mex
mex는 어떤 수열에 포함되지 않은 수 중에서 가장 작은 음이 아닌 정수를 찾는 함수이다.
https://www.acmicpc.net/problem/16902

• 16902 xor을 하고 나면 300000을 넘어갈 수 있다는 점을 알아야 한다. 이진수에서 $2^0$ ~ $2^{18}$ 을 모두 생각해야 하므로 모두 1이 들어갈 경우에는 $2^{19} - 1$ 까지 가능하므로 MAX를 $2^{19}$ 로 설정해야 한다.