AC 자동기概述
AC 자동기(Aho-Corasick Automaton)는 여러 개의 패턴을 동시에 검색할 때 사용하는高效的인 알고리즘이다. KMP 알고리즘의 확장판이라고 볼 수 있으며, Trie 트리와 실패 함수(Failure Function)를 결합하여 구현한다. 이 알고리즘은 텍스트 하나에서 여러 개의 패턴이 등장하는 횟수를 모두 찾을 수 있다.문제介绍
본 article에서는 Luogu의 두 가지 문제를 다룬다. 첫 번째는 P3808로, 단순 버전으로서 기본적인 AC 자동기 구현을要求한다. 두 번째는 P3796으로, 강화 버전으로서 패턴 매칭 결과에서 가장 많이 등장한 패턴을 출력해야 한다.
단순 버전 (P3808)
단순 버전에서는 주어진 여러 개의 패턴과 하나의 긴 텍스트가 주어진다. 각 패턴이 텍스트 안에 몇 번 등장하는지 구하면 된다. 핵심 구현 방식은 다음과 같다.
구현 분석
Trie 구조에 모든 패턴을 삽입한 후, BFS를 통해 실패 링크를 구축한다. 이때 각 노드의 실패 링크는 현재 노드에서 매칭이 실패했을 때 이동할 다음 노드를 가리킨다. 텍스트를 순회하면서 현재 문자에 해당하는 자식 노드로 이동하고, 실패 링크를 따라가며 모든 매칭을 검사한다.
한 번 매칭된 패턴은 다시 세지 않도록 num 배열을 -1로 설정하는 기법을 사용한다. 이렇게 하면 중복 카운트를 방지할 수 있다.
구현 코드
#include<bits/stdc++.h>
using namespace std;
struct AhoCorasick {
static const int ALPHABET = 26;
static const int MAXN = 1000005;
struct Node {
int next[ALPHABET];
int fail;
int out;
Node() {
fill(begin(next), end(next), 0);
fail = 0;
out = 0;
}
};
vector<Node> trie;
int nodeCount;
AhoCorasick() {
trie.resize(MAXN);
nodeCount = 0;
}
void reset() {
trie.clear();
trie.resize(MAXN);
nodeCount = 0;
}
void insert(const string& pattern) {
int current = 0;
for(char ch : pattern) {
int idx = ch - 'a';
if(!trie[current].next[idx]) {
trie[current].next[idx] = ++nodeCount;
}
current = trie[current].next[idx];
}
trie[current].out++;
}
void buildFailure() {
queue<int> q;
// 1단계: root의 직접적 자식들 초기화
for(int i = 0; i < ALPHABET; i++) {
int child = trie[0].next[i];
if(child) {
trie[child].fail = 0;
q.push(child);
}
}
// 2단계: BFS를 통한 실패 링크 구축
while(!q.empty()) {
int current = q.front();
q.pop();
for(int i = 0; i < ALPHABET; i++) {
int child = trie[current].next[i];
if(child) {
// 실패 링크 설정: 현재 노드의 실패 링크에서 같은 문자 탐색
trie[child].fail = trie[trie[current].fail].next[i];
q.push(child);
} else {
// 트랜지션 누락 시 실패 링크의 트랜지션 사용
trie[current].next[i] = trie[trie[current].fail].next[i];
}
}
}
}
int search(const string& text) {
int current = 0;
int result = 0;
for(char ch : text) {
int idx = ch - 'a';
current = trie[current].next[idx];
// 실패 링크를 따라가며 매칭 검사
for(int temp = current; temp && trie[temp].out != -1; temp = trie[temp].fail) {
result += trie[temp].out;
trie[temp].out = -1; // 중복 방지
}
}
return result;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if(!(cin >> n)) return 0;
AhoCorasick automaton;
string pattern, text;
for(int i = 0; i < n; i++) {
cin >> pattern;
automaton.insert(pattern);
}
cin >> text;
automaton.buildFailure();
cout << automaton.search(text) << '\n';
return 0;
}
강화 버전 (P3796)
강화 버전은 결과 출력 방식이 다르다. 단순히 총 매칭 횟수를 구하는 것이 아니라, 어떤 패턴이 가장 많이 매칭되었는지 그 패턴들을 모두 출력해야 한다. 이때 num 배열의 용도가 변경된다.
구현 분석
단순 버전에서는 num이 "현재 노드에서 끝나는 패턴의 개수"였으나, 강화 버전에서는 "현재 노드에서 끝나는 패턴의 번호"를 저장한다. 여러 개의 패턴이同一한 노드에서 끝날 수 있으므로, 실제로는 패턴마다 고유한 노드가 존재하도록 관리한다.
매칭 과정에서 각 패턴의 등장 횟수를 별도의 배열에 누적한다. 모든 매칭이结束后, 가장 큰 횟수를 가진 패턴들을 모두 출력하면 된다.
구현 코드
#include<bits/stdc++.h>
using namespace std;
struct AhoCorasick {
static const int ALPHABET = 26;
static const int MAXN = 20005;
struct Node {
int next[ALPHABET];
int fail;
int patternId;
Node() {
fill(begin(next), end(next), 0);
fail = 0;
patternId = 0;
}
};
vector<Node> trie;
int nodeCount;
AhoCorasick() {
trie.resize(MAXN);
nodeCount = 0;
}
void clear() {
trie.clear();
trie.resize(MAXN);
nodeCount = 0;
}
void insert(const string& pattern, int id) {
int current = 0;
for(char ch : pattern) {
int idx = ch - 'a';
if(!trie[current].next[idx]) {
trie[current].next[idx] = ++nodeCount;
}
current = trie[current].next[idx];
}
trie[current].patternId = id;
}
void buildFailure() {
queue<int> q;
for(int i = 0; i < ALPHABET; i++) {
int child = trie[0].next[i];
if(child) {
trie[child].fail = 0;
q.push(child);
}
}
while(!q.empty()) {
int current = q.front();
q.pop();
for(int i = 0; i < ALPHABET; i++) {
int child = trie[current].next[i];
if(child) {
trie[child].fail = trie[trie[current].fail].next[i];
q.push(child);
} else {
trie[current].next[i] = trie[trie[current].fail].next[i];
}
}
}
}
void countMatches(const string& text, vector<int>& countArray) {
int current = 0;
for(char ch : text) {
int idx = ch - 'a';
current = trie[current].next[idx];
for(int temp = current; temp; temp = trie[temp].fail) {
int pid = trie[temp].patternId;
if(pid) {
countArray[pid]++;
}
}
}
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
while(cin >> n) {
if(n == 0) break;
AhoCorasick automaton;
automaton.clear();
vector<string> patterns(n + 1);
for(int i = 1; i <= n; i++) {
cin >> patterns[i];
automaton.insert(patterns[i], i);
}
string text;
cin >> text;
automaton.buildFailure();
vector<int> matchCount(n + 1, 0);
automaton.countMatches(text, matchCount);
int maxCount = 0;
for(int i = 1; i <= n; i++) {
maxCount = max(maxCount, matchCount[i]);
}
cout << maxCount << '\n';
for(int i = 1; i <= n; i++) {
if(matchCount[i] == maxCount) {
cout << patterns[i] << '\n';
}
}
}
return 0;
}
핵심 구현 포인트
AC 자동기 구현 시 몇 가지 중요한 포인트가 있다. 첫째, 트랜지션 테이블의 누락된 간선을 실패 링크를 통해 다른 노드로 연결하는 최적화를 반드시 적용해야 한다. 이를 통해 매칭 시 매번 실패 링크를 따라가지 않아도 된다. 둘째, 단순 버전에서는 중복 카운트 방지를 위해 한 번 매칭된 노드를 표시하지만, 강화 버전에서는 각 패턴별 등장 횟수를 누적해야 하므로 다른 접근이 필요하다.
두 문제 모두 시간 복잡도는 O(텍스트 길이 + 모든 패턴 길이의 합 + 알파벳 크기 × 노드 수)이며, 실제 구현에서는 BFS 구축 단계에서 알파벳 크기 × 노드 수의 작업이 수행된다.