자동기와 문자열 알고리즘의 연결 고리

문자열 처리 알고리즘에서 KMP, 트라이(Trie), AC 자동기(Aho-Corasick Automaton) 등은 각각 독특한 구조를 가지며, 이들의 핵심 개념은 모두 유한 상태 기계(Finite State Machine)에 근거한다. 이는 입력 문자열을 하나씩 소비하면서 내부 상태를 전이시키고, 특정 조건에서 패턴 일치를 감지하는 방식으로 동작한다.

상태 기계란, 유한 개의 상태와 그 사이의 전이 규칙으로 구성된 시스템이다. 시작 상태에서 출발해 입력 문자에 따라 상태를 전환하며, 최종 상태가 '수용 상태(accepting state)'라면 해당 입력은 인식된 것으로 간주된다. 이 모델은 단순히 "일치 여부"를 판단하는 데 그치지 않고, 각 상태에서 추가적인 정보를 누적하거나 집계하는 데에도 활용된다.

기본 구성 요소: 트라이 구조

여러 문자열 패턴을 동시에 검색해야 할 때, 각 문자열을 개별적으로 비교하는 것은 비효율적이다. 이를 해결하기 위해 사용되는 자료구조가 바로 트라이다. 트라이는 공통 접두사를 공유하는 노드로 구성되어 있으며, 문자열 집합 \( S \) 에 대해 \( s \in S \) 인 경우에만 입력 문자열을 수용한다.

트라이는 문자 단위로 분기하며, 각 노드는 현재까지 매칭된 접두사에 대응된다. 삽입과 탐색 연산은 \( O(m) \) 시간이 소요되며 (여기서 \( m \) 은 문자열 길이), 전체 복잡도는 문자열 집합의 총 길이보다 문자 집합 크기 \( |\Sigma| \) 의 영향을 더 크게 받는다. 특히 \( |\Sigma| \) 가 작을 경우 매우 효율적이다.

KMP 자동기: 단일 패턴의 지능적 전이

KMP 알고리즘은 실패 링크(failure link)를 이용해 불일치 발생 시 불필요한 재검사를 피한다. 이 개념을 자동기로 확장하면, KMP 자동기가 된다. 이 자동기는 주어진 패턴 \( S \) 의 모든 접두사에 대해 상태를 정의하고, 각 상태는 현재 텍스트의 접미사와 \( S \) 의 접두사가 얼마나 길게 일치하는지를 나타낸다.

예를 들어, 패턴 abacaba 에 대해 상태 3은 접두사 aba 와 일치함을 의미한다. 다음 문자가 c 라면 상태 4로 전이되지만, b 라면 실패 함수를 통해 상태 1로 되돌아간 후 재시도한다. 이 과정은 실패 링크를 따라 올라가는 KMP의 pi 배열 계산과 동일하다.

핵심 아이디어는, 현재 상태에서 다음 문자에 따라 가능한 전이를 미리 계산해 두는 것이다. 이렇게 하면 텍스트 \( T \) 를 한 번만 스캔하면서 모든 위치에서의 일치 여부를 판단할 수 있다.

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

const int MAXN = 1e6 + 5;
int fail[MAXN];
int trans[MAXN][26];
string pattern;

void build_kmp_automaton() {
    int n = pattern.size();
    fail[0] = 0;
    for (int i = 1; i < n; ++i) {
        int j = fail[i - 1];
        while (j > 0 && pattern[j] != pattern[i]) {
            j = fail[j - 1];
        }
        if (pattern[j] == pattern[i]) ++j;
        fail[i] = j;
    }

    // 전이 함수 구성
    for (int i = 0; i <= n; ++i) {
        for (char c = 'a'; c <= 'z'; ++c) {
            if (i < n && c == pattern[i]) {
                trans[i][c - 'a'] = i + 1;
            } else {
                int j = i;
                while (j > 0 && (!j || pattern[j] != c)) {
                    j = fail[j - 1];
                }
                if (j && pattern[j] == c) ++j;
                trans[i][c - 'a'] = j;
            }
        }
    }
}

AC 자동기: 다중 패턴의 통합 매칭

AC 자동기는 트라이와 KMP의 아이디어를 결합하여 여러 패턴을 동시에 처리할 수 있도록 설계되었다. 각 패턴을 트라이에 삽입한 후, 모든 노드에 대해 실패 포인터(fail)를 계산한다. 이 포인터는 현재 접미사와 일치하는 가장 긴 다른 패턴의 접두사로 연결된다.

실패 포인터는 너비 우선 탐색(BFS) 방식으로 구성되며, 부모 노드의 실패 포인터를 기반으로 자식 노드의 실패 대상을 결정한다. 즉, 상태 \( u \) 에서 문자 \( c \) 로 갈 수 있는 자식이 없으면, \( \text{fail}[u] \) 에서 \( c \) 로 갈 수 있는 경로를 따라가며 유효한 전이를 찾는다.

이렇게 구성된 자동기를 사용하면, 텍스트를 한 번만 순회하면서 모든 패턴의 출현 횟수를 세거나 위치를 기록할 수 있다. 다만, 어떤 노드가 여러 패턴의 종료점일 수 있으므로, 실패 포인터를 따라 올라가며 모든 일치를 수집해야 한다.

기본 문제: 패턴 존재 여부 확인

가장 간단한 형태는 각 패턴이 최소 한 번이라도 등장했는지를 판단하는 것이다. 이때는 중복 카운팅을 피하기 위해 방문 마킹을 사용한다.

확장 문제: 각 패턴의 등장 횟수 계산

더 복잡한 요구 사항은 각 패턴이 몇 번 등장했는지를 정확히 세는 것이다. 이 경우, 단순히 방문한 노드에서 카운트를 증가시키는 것이 아니라, 전체 경로 상에서 거친 모든 노드의 빈도를 집계한 후, 실패 트리 위에서 위상 정렬처럼 하향 전파해야 한다.

struct AhoCorasick {
    static const int ALPHA = 26;
    vector<array<int, ALPHA>> go;
    vector<int> fail, cnt, indeg;
    int node_count;

    AhoCorasick() : node_count(1) {
        go.emplace_back();
        fill(go[0].begin(), go[0].end(), 0);
        fail.push_back(0);
        cnt.push_back(0);
        indeg.push_back(0);
    }

    void insert(const string& s, int id) {
        int u = 0;
        for (char c : s) {
            int idx = c - 'a';
            if (go[u][idx] == 0) {
                go[u][idx] = node_count++;
                go.emplace_back();
                fill(go.back().begin(), go.back().end(), 0);
                fail.push_back(0);
                cnt.push_back(0);
                indeg.push_back(0);
            }
            u = go[u][idx];
        }
        cnt[u]++;  // 종료 노드에 카운트 증가
    }

    void build() {
        queue<int> q;
        for (int c = 0; c < ALPHA; ++c) {
            if (go[0][c] != 0) {
                q.push(go[0][c]);
            }
        }

        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int c = 0; c < ALPHA; ++c) {
                int &v = go[u][c], f = go[fail[u]][c];
                if (v) {
                    fail[v] = f;
                    cnt[v] += cnt[f];  // 선택적: 전파 시점 조정 가능
                    q.push(v);
                } else {
                    v = f;
                }
            }
        }
    }

    vector<int> query(const string& text) {
        vector<int> freq(node_count, 0);
        int u = 0;
        for (char c : text) {
            u = go[u][c - 'a'];
            freq[u]++;
        }

        // 위상 정렬 기반 전파
        vector<int> order;
        queue<int> q;
        for (int i = 1; i < node_count; ++i) {
            indeg[fail[i]]++;
        }
        for (int i = 1; i < node_count; ++i) {
            if (indeg[i] == 0) q.push(i);
        }
        while (!q.empty()) {
            int u = q.front(); q.pop();
            order.push_back(u);
            if (fail[u] && --indeg[fail[u]] == 0) {
                q.push(fail[u]);
            }
        }

        reverse(order.begin(), order.end());
        for (int u : order) {
            freq[fail[u]] += freq[u];
        }

        return freq;
    }
};

결론 및 주의사항

AC 자동기는 이름에서 오는 오해와 달리, 문제를 자동으로 맞추게 해주지 않는다. 오히려 잘못 구현하면 WA를 유도하기 쉽다. 핵심은 실패 포인터의 정확한 구성과, 결과 집계 방식의 적절한 선택이다. 특히 여러 패턴이 서로 부분 문자열 관계에 있을 경우, 중복 계산이나 누락이 발생하지 않도록 신경 써야 한다.

또한, 실제 응용에서는 메모리 사용량과 전이 속도 사이의 트레이드오프도 고려해야 한다. 예를 들어, 희소한 알파벳에서는 맵 기반 전이를, 밀집된 경우에는 배열 기반을 선호할 수 있다.