AhoCorasick

KMP가 긴 문자열에 어떤 짧은 문자열 하나가 몇 번 나타나는지 검색하는 알고리즘이었다면 AhoCorasick은 여러 개의 짧은 문자열들이 몇 번 나타나는지 검색하는 알고리즘이다. 여러 문자열이 얼마나 나타나는지 KMP를 사용해 확인하려면 (문자열의 개수)$\times$(문자열의 길이)만큼의 시간이 걸릴 텐데 AhoCorasick을 사용하면 선형시간만에 해결할 수 있다.

먼저 트라이라는 자료구조를 알아야 한다. 트라이는 문자를 간선으로 사용하는 트리인데 루트에서 아래로 내려가면서 문자열을 검색할 수 있다. 다음 그림을 보자.

트라이에 a,ba,bab,bc 네 문자열을 넣은 상태이다. 각 문자열의 마지막 노드를 회색으로 칠해 놓았다. 이렇게 여러 문자열을 저장해두면 특정 문자열이 존재하는지 선형시간 만에 확인할 수 있다.

이제 트라이에서 문자열 검색을 하기 위해 실패함수를 만들면 아호코라식을 사용할 수 있다. 실패함수를 만드는 것은 KMP때와 비슷하다. 현재 노드의 실패함수를 만들기 위해 먼저 부모의 실패함수를 보고 매칭에 실패하면 재귀적으로 실패함수를 보면서 될 때까지 확인한다.

실패함수를 만들고 나서 어떤 문자열과 매칭에 성공했는지 확인하는 작업을 주의해야 한다. 위의 그림에서 ba까지 매칭이 성공했으면 ba만 성공한 것이 아니라 a도 성공한 것이다. 즉, 자신 뿐만 아니라 다른 문자열과도 매칭에 성공할 수 있는데 어떤 문자열과 매칭에 성공하였는지 확인은 실패함수를 통해 하면 된다. 어떤 문자열과 매칭에 성공했으면 그 문자열의 접미사와도 매칭에 성공한 것인데 이는 실패함수를 통해 확인할 수 있기 때문이다. 따라서, 실패함수를 만들면서 실패함수에 해당하는 노드가 회색이면 자신도 회색으로 칠해주어야 모든 문자열에 대한 매칭을 확인할 수 있다. 모든 문자열에 대해 나타나는 위치를 구하려면 해당 노드까지 매칭에 성공했을 경우 매칭에 성공한 문자열들을 리스트로 연결해주어야 하는데 실패함수를 보고 연결해 주면 된다.

실패함수를 구할 때에는 자신보다 깊이가 낮은 노드들의 실패함수가 구해져 있어야 하기 때문에 너비 우선탐색으로 노드들을 탐색해가며 실패함수를 구하면 된다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

int toInt(char x){     return x-'a'; }   struct trie{     trie *child[26],*fail,*link;     bool terminal;       int id,cnt;     static int N;           trie():fail(NULL),link(NULL),terminal(false),id(N++),cnt(0){         memset(child,NULL,sizeof(child));     }     ~trie(){         for(int i=0;i<26;i++){             if(child[i])delete child[i];         }     }       void add(char *x){         if(*x==NULL){             terminal=true;             cnt++;             return;         }         int i=toInt(*x);         if(child[i]==NULL)child[i]=new trie();         child[i]->add(x+1);     } };   int trie::N = 0; trie *root = new trie();   void failureFunction(){     queue<trie*> Q;     Q.push(root);     while(!Q.empty()){         trie *p=Q.front();Q.pop();         for(int i=0;i<26;i++){             trie *v=p->child[i];             if(v==NULL)continue;             trie *t=p->fail;             while(t&&t->child[i]==NULL)t=t->fail;             if(t)v->fail=t->child[i];             else v->fail=root;               v->cnt+=v->fail->cnt;             if(v->fail->terminal)v->link=v->fail;             else v->link=v->fail->link;             Q.push(v);         }     } }   int ahoCorasick(char *x,trie *v){     if(*x==NULL)return v->cnt;     int i=toInt(*x);     trie *t=v;     while(t&&t->child[i]==NULL)t=t->fail;     if(t)return v->cnt+ahoCorasick(x+1,t->child[i]);     return v->cnt+ahoCorasick(x+1,root); }

위의 코드는 짧은 문자열들이 긴 문자열에 얼마나 나타나는지 선형시간에 확인할 수 있다. 각 문자열들이 나타나는 각각의 위치는 최대 $\BigO{N^2}$개 이므로 모든 위치를 구하는 것은 선형시간에 할 수가 없다. 위의 코드에서 link를 보며 따라가면 어떤 문자열과 매칭에 성공했는지 확인할 수 있다.