# Trie와 Aho-Corasick

Trie는 문자열들을 글자 단위로 공유해서 저장하는 트리입니다. 한 패턴을 찾을 때는 KMP나 Z algorithm이 충분하지만, 패턴이 수천 개 이상이고 텍스트를 한 번만 훑어야 한다면 Trie에 실패 링크를 붙인 Aho-Corasick을 씁니다.

## Trie가 필요한 상황

단어 집합이 있고 접두사 기준으로 빠르게 탐색해야 하면 Trie를 떠올립니다.

| 문제 신호 | Trie 관점 |
| --- | --- |
| 사전에 있는 단어인지 많이 확인한다 | 루트에서 글자를 따라 내려간다 |
| 어떤 문자열이 다른 문자열의 접두사인지 본다 | 중간 노드의 종료 표시를 본다 |
| 자동완성 후보를 찾는다 | 접두사 노드의 서브트리를 훑는다 |
| 여러 패턴을 동시에 찾아야 한다 | Trie에 실패 링크를 붙여 Aho-Corasick으로 확장한다 |

Trie의 한 노드는 "지금까지 읽은 접두사"를 뜻합니다. 같은 접두사를 가진 문자열들은 같은 경로를 공유하므로, 전체 저장 공간은 문자열 길이 합에 비례합니다.

## 배열 기반 Trie

알파벳 소문자만 다루는 문제라면 각 노드에 `26`개 자식 인덱스를 둘 수 있습니다. 문자가 더 다양하면 `map`이나 압축 인덱스를 쓰지만, 대회 문제에서는 배열 Trie가 빠르고 단순합니다.

> **코드 환경: 일반 C++17 학습용.** 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 [공통 코드](https://h.readiz.com/learn/cpp-common-library)와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

```cpp compile-check
#include <array>
#include <string>
#include <vector>
using namespace std;

struct TrieNode {
    array<int, 26> next;
    int terminalCount;

    TrieNode() : terminalCount(0) {
        next.fill(-1);
    }
};

struct Trie {
    vector<TrieNode> nodes;

    Trie() {
        nodes.push_back(TrieNode());
    }

    void insert(const string& word) {
        int current = 0;
        for (char ch : word) {
            int c = ch - 'a';
            if (nodes[current].next[c] == -1) {
                nodes[current].next[c] = (int)nodes.size();
                nodes.push_back(TrieNode());
            }
            current = nodes[current].next[c];
        }
        ++nodes[current].terminalCount;
    }

    bool contains(const string& word) const {
        int current = 0;
        for (char ch : word) {
            int c = ch - 'a';
            if (nodes[current].next[c] == -1) {
                return false;
            }
            current = nodes[current].next[c];
        }
        return nodes[current].terminalCount > 0;
    }
};
```

`terminalCount`는 같은 단어가 여러 번 들어올 수 있는 경우를 처리하기 위해 개수로 둔 값입니다. 중복이 의미 없으면 `bool terminal`만 둬도 됩니다.

## Aho-Corasick의 실패 링크

Aho-Corasick은 Trie 위에 KMP의 실패 함수와 비슷한 링크를 붙입니다. 현재 노드가 나타내는 문자열 뒤에 글자 `c`를 붙였는데 Trie 경로가 없다면, 가능한 가장 긴 접미사 상태로 이동해서 다시 시도합니다.

예를 들어 패턴이 `he`, `she`, `his`, `hers`라면 `she`를 읽은 상태에는 패턴 `he`도 접미사로 숨어 있습니다. 실패 링크와 출력 전파가 있어야 이런 겹친 패턴을 놓치지 않습니다.

실패 링크는 BFS 순서로 만듭니다. 부모의 실패 링크가 이미 계산되어 있어야 자식의 실패 링크를 정할 수 있기 때문입니다.

```cpp compile-check
#include <array>
#include <queue>
#include <string>
#include <vector>
using namespace std;

struct AhoNode {
    array<int, 26> next;
    int fail;
    int outputCount;

    AhoNode() : fail(0), outputCount(0) {
        next.fill(-1);
    }
};

struct AhoCorasick {
    vector<AhoNode> nodes;

    AhoCorasick() {
        nodes.push_back(AhoNode());
    }

    void insert(const string& pattern) {
        int current = 0;
        for (char ch : pattern) {
            int c = ch - 'a';
            if (nodes[current].next[c] == -1) {
                nodes[current].next[c] = (int)nodes.size();
                nodes.push_back(AhoNode());
            }
            current = nodes[current].next[c];
        }
        ++nodes[current].outputCount;
    }

    void build() {
        queue<int> q;
        for (int c = 0; c < 26; ++c) {
            int child = nodes[0].next[c];
            if (child == -1) {
                nodes[0].next[c] = 0;
            } else {
                nodes[child].fail = 0;
                q.push(child);
            }
        }

        while (!q.empty()) {
            int current = q.front();
            q.pop();

            nodes[current].outputCount += nodes[nodes[current].fail].outputCount;

            for (int c = 0; c < 26; ++c) {
                int child = nodes[current].next[c];
                if (child == -1) {
                    nodes[current].next[c] = nodes[nodes[current].fail].next[c];
                    continue;
                }
                nodes[child].fail = nodes[nodes[current].fail].next[c];
                q.push(child);
            }
        }
    }

    long long countMatches(const string& text) const {
        long long matches = 0;
        int current = 0;
        for (char ch : text) {
            int c = ch - 'a';
            current = nodes[current].next[c];
            matches += nodes[current].outputCount;
        }
        return matches;
    }
};
```

패턴과 텍스트는 소문자이며, 패턴은 비어 있지 않아야 합니다. 모든 패턴 삽입 후 `build()`를 한 번 호출하고 이후 패턴을 추가하지 않습니다. 새 패턴 집합은 새 객체로 만듭니다. 위 구현은 `build()`에서 없는 전이를 미리 채웁니다. 그래서 검색 중에는 `while`로 실패 링크를 따라가지 않고 `current = next[current][c]` 한 번으로 이동합니다.

## 무엇을 세야 하는지 먼저 정하기

Aho-Corasick 문제는 구현보다 집계 방식에서 더 자주 틀립니다.

| 요구 | 필요한 정보 |
| --- | --- |
| 패턴이 하나라도 등장하는가 | `outputCount > 0` 여부 |
| 모든 등장 횟수 합 | 실패 링크 조상 출력을 더한 `outputCount` |
| 각 패턴별 등장 횟수 | terminal 노드 id와 fail tree 누적 |
| 등장 위치 출력 | 패턴 길이와 현재 텍스트 인덱스 |
| 금지 패턴을 피하는 DP | automaton 상태와 `outputCount == 0` 조건 |

각 패턴별 등장 횟수를 모두 구해야 할 때는 검색 중 방문한 상태 횟수를 세고, 실패 링크로 만든 트리에서 자식의 방문 수를 부모로 올리는 방법을 많이 씁니다. 패턴 노드에 누적된 방문 수가 그 패턴의 등장 횟수입니다.

패턴 ID 목록을 각 실패 링크에서 복사하면 공간·시간이 커질 수 있습니다. 개수만 필요하면 `outputCount`를, 패턴별 횟수면 방문 수의 실패 링크 누적을 사용합니다.

## 시간 복잡도

| 작업 | 시간 | 메모리 |
| --- | ---: | ---: |
| Trie 삽입 | 전체 패턴 길이 합 `O(S)` | `O(S * alphabet)` 또는 sparse 구조 |
| 실패 링크 생성 | `O(S * alphabet)` | Trie 노드 배열 |
| 텍스트 검색 | `O(N)` | 검색 상태 `O(1)` |
| 각 패턴별 누적 | `O(S + N)` | fail tree와 방문 수 |

알파벳이 `26`보다 훨씬 크면 모든 노드에 전체 alphabet 배열을 두는 방식이 부담됩니다. 이때는 문자 압축, `unordered_map`, 정렬된 edge list 같은 sparse 표현을 검토합니다.