String Matching Algorithms

1) Knuth-Morris-Pratt Algorithm

2) Aho-Corasick Algorithm

1) Knuth-Morris-Pratt Algorithm

KMP Algorithm은 패턴 $P$와 문자열 $S$가 있을 때, 문자열 $S$에 패턴 $P$가 부분문자열로 있는지, 혹은 몇 개 있는지 선형시간 $O(|S| + |P|)$에 확인하는 방법이다.

 

기본적인 아이디어는 실패 함수 f(i)에서 온다. 아래는 패턴 $P$가 "abracadabra" 일 때 실패 함수 값을 표로 나타낸 것이다.

i	1	2	3	4	5	6	7	8	9	10	11
P	a	b	r	a	c	a	d	a	b	r	a
f	0	0	0	1	0	1	0	1	2	3	4

 

$P[i, j]$를 패턴 $P$의 $i$번째 문자부터 $j$번째 문자까지로 구성된 부분문자열이라 하자. 실패 함수 $f(i)$는 $i$ 보다 작은 값이며, $P[i-f(i)+1, i]$와 $P[1, f(i)]$가 같도록 되는 최대값으로 정의된다.

 

패턴 $P$의 실패함수는 아래처럼 $O(|P|)$에 계산할 수 있다.

int k = 0; F[1] = 0; for (int i=2;i<=|P|;i++){ while (k && P[k+1] != P[i]) k = F[k]; if (P[k+1] == P[i]) k++; F[i] = k; }

위 방법의 시간복잡도가 $O(|P|)$라는 것을 쉽게 보이기 위해서는 4번째 줄의 while문에 집중할 필요가 있다. while문을 한 번 돌 수록 변수 k는 적어도 1 감소하게된다. 변수 k는 0에서부터 시작해서 최대 $|P|$ 만큼 증가하므로 감소 또한 최대 $|P|$번 일어날 수 있다. 따라서 전체 시간복잡도가 $O(|P|)$가 된다.

 

실패 함수를 계산하는 것과 문자열 $S$에 패턴 $P$가 존재하는지 확인하는 것은 완전히 똑같다.

int k = 0; for (int i=1;i<=|S|;i++){ while (k && P[k+1] != S[i]) k = F[k]; if (P[k+1] == S[i]) k++; if (k == |P|){ // MATCHED WITH S[i-|P|+1, i]!! k = F[k]; } }

실패 함수를 구할 때와 마찬가지의 이유로 시간복잡도가 $O(|S|)$이다.

2) Aho-Corasick Algorithm

Aho-Corasick Algorithm은 KMP Algorithm과 거의 흡사하다. 하나의 차이점이 있다면 패턴이 한 종류일 때 쓰는 KMP Algorithm과 달리 Aho-Corasick Algorithm은 패턴이 여러 개일 때 사용하는 방법이다. 시간복잡도는 $O(|S| + \sum{|P_i|})$이다.

 

Aho-Corasick Algorithm에서 패턴들을 Trie로 나타낼 수 있다. 예를 들어 패턴이 {"he", "she", "his", "hers"}라고 했을 때 아래처럼 Trie를 구성할 수 있다.

KMP Algorithm에서는 실패 함수 값을 하나의 수(길이값)로 표현하지만 Aho-Corasick Algorithm에서는 노드에서 비슷한 원리로 실패 링크를 만들 수 있다. 위 Trie에서 실패 링크를 포함 시키면 아래 그림처럼 된다. 아래 링크에서는 실패 링크를 점선으로 표현했다.

위 Trie를 구성하는 시간복잡도는 $O(\sum{|P_i|}$ 이다. Trie를 구현하고 문자열 $S$에 대해 탐색하는 것도 KMP Algorithm과 마찬가지로 하면 된다. 문자열에 대해 매칭을 검색하는 시간복잡도느 $O(|S|)$가 된다. 간단한 Aho-Corasick Algorithm 구현 문제로는 BOJ 9250번 - 문제열 집합 판별 문제가 있다.

 

Aho-Corasick Algorithm에서는 패턴이 여러 개이기 때문에 실패 링크 외에도 출력 링크라는 것이 필요하다. 어떤 패턴이 다른 패턴의 substring인 상황(위 그림에서 he는 she의 substring)인 경우에 패턴을 찾지 못할 수 있기 때문에 필요한 것이다. 어떤 노드의 출력 링크란 그 노드를 포함하여 실패 링크를 따라가다 만나는 패턴의 끝을 나타내는 노드를 향하는 링크를 의미한다.

 

아래 코드는 Aho-Corasick 구현 및 각 패턴이 문자열에 몇번 등장하는지 계산하는 코드다.

 

#include <bits/stdc++.h> using namespace std; #define pb push_back #define all(v) (v).begin(), (v).end() constexpr int MAXM = 100005, MAXL = 300005; int N, M; char S[MAXL], buf[MAXL]; struct NODE{ bool is_end = 0; int count = 0; NODE *nxt[26]{}, *f = nullptr, *o = nullptr; // f = 실패 링크, o = 출력 링크 } *root; NODE *my_end_node[MAXM]; int main(){ scanf("%s%d", S+1, &M); N = strlen(S+1); // 입력과 동시에 Trie 구성 root = new NODE(); for (int i=1;i<=M;i++){ scanf("%s", buf+1); int n=strlen(buf+1); NODE *now=root; for (int j=1;j<=n;j++){ char c = buf[j] - 'a'; if (!now->nxt[c]) now->nxt[c] = new NODE(); now = now->nxt[c]; } now->is_end = 1; my_end_node[i] = now; } // BFS를 통해 실패 링크와 출력 링크를 계산 queue<NODE*> que; for (int i=0;i<26;i++) if (root->nxt[i]){ root->nxt[i]->f = root; que.push(root->nxt[i]); } while (!que.empty()){ NODE *q = que.front(); que.pop(); if (q->is_end) q->o = q; else q->o = q->f->o; for (int i=0;i<26;i++) if (q->nxt[i]){ NODE *t = q->nxt[i]; t->f = q->f; while (t->f != root && !t->f->nxt[i]) t->f = t->f->f; if (t->f->nxt[i]) t->f = t->f->nxt[i]; que.push(t); } } // 문자열 S에서 패턴 검색 NODE *now = root; for (int i=1;i<=N;i++){ int c = S[i] - 'a'; while (now !=root && !now->nxt[c]) now = now->f; if (now->nxt[c]) now = now->nxt[c]; if (now->o){ // 패턴 발견! now->o->count++; } } // 패턴 등장 회수 누적 계산 (BFS 역순으로) vector<NODE*> order; que.push(root); while (!que.empty()){ NODE *q = que.front(); que.pop(); order.pb(q); for (int i=0;i<26;i++) if (q->nxt[i]) que.push(q->nxt[i]); } reverse(all(order)); for (NODE* now: order){ if (now->is_end && now->f->o) now->f->o->count += now->count; } for (int i=1;i<=M;i++) printf("pattern #%d occurs %d times\n", i, my_end_node[i]->count); }