아호코라식 (Aho-Corasick)

아호코라식은 문자열에서의 패턴 매칭 알고리즘이다. 길이 $N$의 문자열 $S$와 패턴 $T_1, T_2, ..., T_k$($T_i$의 길이는 $M_i$)이 주어졌을 때, 각 패턴이 문자열의 어디에서 나타나는지를 시간복잡도 $O(N+M_1+...+M_k)$만에 찾아낼 수 있다.

 

Naive하게 찾으면 $O(N(M_1+...+M_k))$이고, KMP를 사용하면 $O(Nk+M_1+...+M_k)$라는 점을 감안하면 놀라운 시간복잡도이다.

 

방법은 KMP+트라이이다. KMP에서는 failure function을 정의했다. 이는 각 prefix $T[0, i-1]$에 대하여, prefix이면서 동시에 suffix인 가장 긴 substring을 나타냈다. failure function을 계산한 후에는, $S$에서 $T$를 찾다가 match가 되지 않을 경우 failure function을 타고 가서 그 지점부터 매치를 다시 하면 되었다. 아호코라식에서는 패턴들로 트라이를 만든 후 거기서 failure function을 계산한다.

 

트라이에서 각 패턴이 끝나는 지점에는 표시를 해둔다. 그리고 어떤 노드의 failure function이 가르키는 노드가 표시되어있다면, 이 노드에도 표시를 해준다. 이는 패턴끼리 substring 관계일 수 있기 때문에 필요한 작업이다. 

 

아래 링크를 통해 공부하였다.

https://m.blog.naver.com/kks227/220992598966

 

 

아래는 코드이다. 자식 노드가 없는 부분들을 failure function을 이용해 연결해주는 부분은 문제 특성 상 failure function을 반복적으로 따라가야 하는 경우에 시간복잡도가 커지지 않도록 하기 위해 필요하다. (ex. 백준 10745번 Censoring) 그러나 이렇게 할 경우 포인터 상에 사이클이 생겨 delete 연산이 제대로 작동하지 않는다.

 

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

#define eb emplace_back

const int MAXN = 100010;

struct NOD {
	NOD *chi[26];
	NOD *fail;
	bool e;

	NOD() {
		for(int i = 0; i < 26; i++) chi[i] = 0;
		e = false;
	}

	~NOD() {
		for(int i = 0 ; i < 26; i++) if(chi[i]) delete chi[i];
	}
};

char S[MAXN];
string T[MAXN];

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N;

	cin >> S;
	cin >> N;
	for(int i = 0; i < N; i++) cin >> T[i];

	// 트라이 생성
	NOD *r = new NOD();
	for(int i = 0; i < N; i++) {
		NOD *n = r;
		for(auto a : T[i]) {
			if(!n->chi[a - 'a']) n->chi[a - 'a'] = new NOD();
			n = n->chi[a - 'a'];
		}
		n->e = true;
	}
	
	// bfs로 failure function 계산
	queue<NOD*> q;
	q.push(r);
	r->fail = r;
	while(!q.empty()) {
		NOD *n = q.front();
		q.pop();
		for(int i = 0; i < 26; i++) if(n->chi[i]) {
			if(n == r) n->chi[i]->fail = r;
			else {
				NOD *t = n->fail;
				while(t != r && !t->chi[i]) t = t->fail;
				n->chi[i]->fail = t->chi[i] ? t->chi[i] : t;
			}
			// 패턴이 끝나는 지점 체크
			n->chi[i]->e |= n->chi[i]->fail->e;
			q.push(n->chi[i]);
		}
	}

	// 다음 노드로 이동하고자 할 때 failure function을 여러 번 타는 대신 바로 이동할 수 있도록 연결해주기
	for(int i = 0; i < 26; i++) {
		if(r->chi[i]) q.push(r->chi[i]);
		else r->chi[i] = r;
	}
	while(!q.empty()) {
		NOD *n = q.front();
		q.pop();
		for(int i = 0; i < 26; i++) {
			if(n->chi[i]) q.push(n->chi[i]);
			else n->chi[i] = n->fail->chi[i];
		}
	}

	// 문자열 매칭
	NOD *n = r;
	for(int i = 0; S[i]; i++) {
		n = n->chi[S[i] - 'a'];
		if(n->e) {/*TODO*/}
	}

	return 0;
}