Aho-Corasick (아호-코라식)

정의

Aho-Corasick 은 Alfred Aho 와 Margaret Corasick 이 1975년 고안한 다중 패턴 문자열 매칭 알고리즘. Trie 에 KMP failure function 을 결합해 여러 패턴을 한 번의 텍스트 순회로 모두 찾는다. O(N + M + matches) (N = 텍스트 길이, M = 총 패턴 길이).

문제 상황과 동기

악성코드 시그니처 k 개를 네트워크 패킷 T 에서 모두 탐지해야 한다.

• naive: 각 패턴마다 KMP → O(k x (N + |pi|)). k = 10^4, N = 10^6 이면 10^10.
• Aho-Corasick: 한 번의 Trie 순회. O(N + M + matches).

핵심 통찰: Trie 에서 mismatch 시 failure link 를 따라가면, 이미 스캔한 접미사 중 가장 긴 패턴 접두사로 즉시 이동. KMP 의 π 를 Trie 로 일반화.

시각화

핵심 아이디어

1. Trie 구축

모든 패턴을 Trie 에 삽입. 각 노드에 output (패턴 완성) 표시.

2. Failure link (BFS)

루트 직계 자식 → fail = 루트
BFS:
  for 자식 u of v (c):
    f = fail[v]
    while f && !trie[f][c]: f = fail[f]
    if trie[f][c]: f = trie[f][c]
    fail[u] = f
    output[u] |= output[f]

3. 매칭

텍스트를 한 문자씩 읽으며 Trie 이동. 현재 노드나 failure link 에 output 이 있으면 매치.

invariant: 현재 노드 = 텍스트 접미사 중 가장 긴, 어떤 패턴의 접두사.

알고리즘

insert(s):
    v = root
    for ch in s:
        if !trie[v][c]: trie[v][c] = new_node()
        v = trie[v][c]
    term[v] = true

build():
    q = queue(root 의 자식)
    while q:
        v = q.pop()
        for c in 0..25:
            u = trie[v][c]; if !u: continue
            f = fail[v]
            while f && !trie[f][c]: f = fail[f]
            if trie[f][c]: f = trie[f][c]
            fail[u] = f; term[u] |= term[f]; q.push(u)

search(text):
    v = 0; cnt = 0
    for ch in text:
        c = ch - 'a'
        while v && !trie[v][c]: v = fail[v]
        if trie[v][c]: v = trie[v][c]
        if term[v]: cnt++
    return cnt

구현

// Aho-Corasick, O(N+M) - Trie + failure link
#include <bits/stdc++.h>
using namespace std;
const int MAX = 10000;
int trie[MAX][26], fail[MAX], term[MAX], idx;
int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
  int n; cin >> n;
  for (int i = 0; i < n; i++) {
      string s; cin >> s; int v = 0;
      for (char ch : s) { int c = ch - 'a';
          if (!trie[v][c]) trie[v][c] = ++idx;
          v = trie[v][c]; }
      term[v] = 1;
  }
  queue<int> q;
  for (int c = 0; c < 26; c++)
      if (trie[0][c]) q.push(trie[0][c]);
  while (!q.empty()) {
      int v = q.front(); q.pop();
      for (int c = 0; c < 26; c++) {
          int u = trie[v][c]; if (!u) continue;
          int f = fail[v];
          while (f && !trie[f][c]) f = fail[f];
          if (trie[f][c]) f = trie[f][c];
          fail[u] = f; term[u] |= term[f]; q.push(u);
      }
  }
  string text; cin >> text; int v = 0, cnt = 0;
  for (char ch : text) { int c = ch - 'a';
      while (v && !trie[v][c]) v = fail[v];
      if (trie[v][c]) v = trie[v][c];
      if (term[v]) cnt++; }
  cout << cnt << "\n";
}

# Aho-Corasick, O(N+M)
from collections import deque
import sys
input = sys.stdin.readline
MAX = 10000
trie = [[0]*26 for _ in range(MAX)]
fail = [0]*MAX; term = [0]*MAX; idx = 0
n = int(input())
for _ in range(n):
  s = input().strip(); v = 0
  for ch in s:
      c = ord(ch)-97
      if not trie[v][c]: idx += 1; trie[v][c] = idx
      v = trie[v][c]
  term[v] = 1
q = deque()
for c in range(26):
  if trie[0][c]: q.append(trie[0][c])
while q:
  v = q.popleft()
  for c in range(26):
      u = trie[v][c]; if not u: continue
      f = fail[v]
      while f and not trie[f][c]: f = fail[f]
      if trie[f][c]: f = trie[f][c]
      fail[u] = f; term[u] |= term[f]; q.append(u)
text = input().strip(); v = 0; cnt = 0
for ch in text:
  c = ord(ch)-97
  while v and not trie[v][c]: v = fail[v]
  if trie[v][c]: v = trie[v][c]
  if term[v]: cnt += 1
print(cnt)

5
he
she
his
hers
her
hershe

4

복잡도

while 로 failure link 를 거슬러 올라가는 비용은 amortized O(M) (BFS 각 노드 1회, 검색 중 v 는 감소 후 증가로 상쇄).

변형 / 활용

1. goto / failure 최적화

trie[v][c] 가 0 이면 trie[fail[v]][c] 로 미리 연결. 검색 while 문 제거 → O(N) strictly.

2. 출력 위치 저장

term 대신 패턴 ID 리스트 저장. 각 노드가 어떤 패턴의 끝인지, failure link 로 전파되는 패턴까지 관리.

3. 2D 격자 패턴 매칭, 악성코드 탐지

Snort / YARA 의 핵심 엔진.

함정

1. failure link 전파

term[v] |= term[fail[v]] 누락 시 “she” 내부의 “he” 를 놓침.

2. 배열 크기

Trie 배열 = Σ|patterns| x Σ 까지. 동적 할당(vector) 추천.

3. 충분하지 않은 while

while 로 failure link 를 끝까지 올라가도 amortized O(N). 최적화로 제거 가능.

BOJ 연습 문제

참고

• 트라이
• KMP 문자열 매칭
• 문자열 기본