아호-코라식

무엇을 해결하나

KMP는 한 패턴을 본문에서 찾는다. 그런데 패턴이 여러 개(\(P_1, \dots, P_k\))
이고, 긴 본문 \(T\)에서 그중 어느 것이든 등장하는 위치를 모두 찾으려면?
각 패턴마다 KMP를 돌리면 \(O(|T| \cdot k)\)로 느리다. 아호-코라식(Aho-Corasick)
은 이를 \(O(|T| + \sum |P_i| + \text{등장 수})\)에 처리한다.

트라이 + 실패 링크

핵심은 두 도구의 결합이다.

1. 트라이(trie): 모든 패턴을 글자 단위로 하나의 접두사 트리에 넣는다. 어떤
   패턴이 끝나는 노드에 "여기서 패턴이 끝난다"는 표시를 단다.
2. 실패 링크(failure link): 본문을 한 글자씩 읽다가 현재 노드에서 다음 글자로
   못 갈 때, 현재까지 읽은 접미사 중 트라이에 존재하는 가장 긴 접두사로
   점프하는 링크. KMP의 실패 함수를 트라이 전체로 일반화한 것이다.

실패 링크의 정의: 노드 \(v\)(루트에서 \(v\)까지 문자열 \(s\))의 실패 링크는,
\(s\)의 진 접미사 중 트라이에 존재하는 가장 긴 것에 대응하는 노드.

실패 링크는 BFS로

실패 링크는 트라이 위에서 BFS(레벨 순) 로 계산한다. 깊이 1 노드의 실패
링크는 루트다. 노드 \(u\)에서 글자 \(c\)로 가는 자식 \(v\)의 실패 링크는
"\(u\)의 실패 링크에서 \(c\)로 갈 수 있는 노드"로 정한다 — KMP의 실패 함수 점화와
정확히 같은 구조다. 자식이 없으면 그 방향 전이를 실패 링크의 전이로 채우는
goto 함수(자동자화) 를 쓰면 본문 처리 시 항상 \(O(1)\)로 다음 상태로 간다.

출력 링크

한 위치에서 끝나는 패턴이 여러 개일 수 있다(예: "she"와 "he"). 그래서 실패
링크를 타고 올라가며 만나는 패턴 끝 노드들을 모두 보고해야 한다. 매번
올라가면 느리므로, 실패 링크 중 가장 가까운 패턴 끝 노드로 바로 가는
출력 링크(dict suffix link) 를 미리 계산해 둔다.

복잡도

트라이 구축 \(O(\sum |P_i|)\), 실패/출력 링크 BFS도 같은 비용, 본문 처리는 한
글자당 \(O(1)\) 전이라 \(O(|T|)\), 거기에 실제 등장 보고 비용을 더한다. KMP가
"한 패턴 자동자"라면 아호-코라식은 "패턴 집합 자동자"다.

아호-코라식 구현 (소문자 알파벳)

go[v][c]를 자동자 전이로 채워 본문 처리 시 분기 없이 진행한다.

#include <bits/stdc++.h>
using namespace std;

const int MAXNODE = 100001, ALPHA = 26;
int go_[MAXNODE][ALPHA];   // 자동자 전이
int fail_[MAXNODE];        // 실패 링크
int out_cnt[MAXNODE];      // 이 노드에서 끝나는 패턴 수(또는 표시)
int node_cnt = 0;

int new_node() {
    int v = ++node_cnt;
    memset(go_[v], 0, sizeof(go_[v]));
    fail_[v] = 0; out_cnt[v] = 0;
    return v;
}
void add_pattern(const string& s) {
    int cur = 0;                       // 0 = 루트
    for (char ch : s) {
        int c = ch - 'a';
        if (!go_[cur][c]) go_[cur][c] = new_node();
        cur = go_[cur][c];
    }
    out_cnt[cur]++;                    // 패턴 끝 표시
}
void build() {                         // BFS로 실패/전이 자동자화
    queue<int> q;
    for (int c = 0; c < ALPHA; c++)
        if (go_[0][c]) { fail_[go_[0][c]] = 0; q.push(go_[0][c]); }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        out_cnt[u] += out_cnt[fail_[u]];   // 출력 링크 효과를 누적
        for (int c = 0; c < ALPHA; c++) {
            int v = go_[u][c];
            if (v) {
                fail_[v] = go_[fail_[u]][c];   // 실패 링크
                q.push(v);
            } else {
                go_[u][c] = go_[fail_[u]][c];  // 없는 전이를 자동자화
            }
        }
    }
}
long long match(const string& text) {  // 본문에서 총 등장 수
    int cur = 0; long long total = 0;
    for (char ch : text) {
        cur = go_[cur][ch - 'a'];          // 항상 O(1) 전이
        total += out_cnt[cur];             // 여기서 끝나는 패턴들
    }
    return total;
}

루트 노드 인덱스 0은 new_node 없이 0으로 두고, go_[0]은 0으로 초기화한
상태에서 시작한다.

흔한 실수

• 루트 전이 초기화 — go_[0][c]가 비어 있으면 루트로(0) 가야 한다. BFS
  시작 시 깊이 1 노드의 실패만 루트로 두고, 빈 루트 전이는 0을 유지한다.
• 출력 링크 누적 시점 — out_cnt[u] += out_cnt[fail_[u]]는 BFS에서 부모가
  먼저 처리됨을 이용한다. 실패 링크의 깊이가 항상 더 얕으므로 레벨 순서로
  누적해야 옳다.
• 무엇을 세는가 — "등장 횟수"인지 "등장한 패턴 종류 수"인지에 따라
  out_cnt의 의미를 다르게 둬야 한다.
• 알파벳 크기 — 대문자/숫자/특수문자가 섞이면 ALPHA와 인덱싱을 맞춘다.
  알파벳이 크면 map 전이를 고려한다.

활용

특히 "금지 문자열을 포함하지 않는 길이 \(L\) 문자열의 수" 같은 카운팅 DP는
아호-코라식 자동자의 상태를 DP 상태로 삼아 행렬 거듭제곱과 결합하는 고전
패턴이다. 아호-코라식은 KMP·트라이를 잇는 다중 패턴 매칭의 표준 해법이다.