Aho-Corasick Multiple Pattern Matching Algorithm

https://www.slideshare.net/ssuser81b91b/ahocorasick-algorithm 

문자열 S와 여러 개의 문자열 T가 주어졌을 때, T에 있는 문자열 중 하나와 S가 매칭이 되는 지를 계산 할 수 있는 알고리즘이다. 선형 시간에 작동한다.

Aho Corasick Algorithm을 알기 위해서는 KMP 알고리즘과 트라이에 대한 이해가 필요하다. KMP 알고리즘에 대한 koosaga.com의 설명

아호 코라식 알고리즘을 한 문장으로 설명하면, KMP에서 사용하는 Failure function을 트라이에 확장시키는 것. 딱 이것으로 끝난다. 스텝도 비슷하다.

 * 1. 트라이가 주어졌을 때 트라이에서 Failure function (Failure link나 Suffix link라고도 부른다) 을 계산하는 것

 * 2. Failure function이 계산된 트라이에서 문자열을 찾는 것

1번이 전처리 과정이므로 당연히 1번이 2번보다 선행되는 과정이다. 하지만 설명의 편의를 위해 2번을 먼저 설명한다.

2. Failure function이 계산된 트라이에서 문자열을 찾는 것

먼저, 트라이에다가 T에 있는 모든 문자열을 저장하는 과정이 필요할 것이다. 문자열을 저장하면서, 마지막 문자가 가리키는 노드에 체크를 해놓자. (output check라고 부르겠다. 보통 output link라고 부르는 것 같은데, 혼란을 주는 이름인 것 같아서 이 설명에서는 새로운 단어를 사용한다.) 이는 "이 노드에 도달했다면 한 문자열과 매칭이 됐다"는 것을 표시해 준다. 당연히 문자열을 찾으면서 알아야 할 정보이기도 하다.

트라이 각 노드의 Failure function은 다음과 같이 정의된다. 

"루트가 아닌 각 노드 v에 대해서, 루트 -> w로 가는 경로가, 루트 -> v로 가는 경로의 suffix이며, w != v이고, 그러한 것이 여러 개 있다면 그 중 가장 긴 것"

이를 사용하면 KMP와 동일한 방법으로 트라이를 따라갈 수 있다. 끝점을 늘려가면서, 만약에 해당 문자열을 포함하는 트라이 상 경로가 있다면 그 곳으로 움직이고, 그렇지 않다면 Failure function을 통해서 skip을 반복하는 방식이다. 이를 반복하면 트라이 상 깊이를 최대로 유지하면서 계속 탐색을 진행할 것이다.

그렇다면, 현재 트라이 상 어떠한 노드 v에 있을 때, 루트 -> v로 가는 경로의 substring 중 T에 속한 문자열이 있는 지를 알 수 있을까? 단순하게 생각하면 v의 output check 여부에 따라서 판정할 수 있을 것 같지만, 트라이 상 깊이를 최대로 유지했기 때문에, 루트 -> v로 가는 경로의 suffix 중에서 T에 속한 문자열이 있다면 이를 찾지 못하게 된다. 

이를 Naive하게 해결하는 방법은, 각각의 노드에 도달했을 때마다 Failure function을 타고 올라가면서, 그 중 output check가 있는 노드의 존재를 확인하는 것이다. 이 방법은 전처리를 통해서 시간 복잡도를 줄일 수 있는데, failure function 역시 트리의 형태를 띄므로 (각각의 노드가 깊이가 작은 노드 정확히 한개를 부모로 가지고 있으며, 모든 노드에서 루트로 도달 가능하다.) failure function tree에서 자식으로 dfs나 bfs로 output check를 뿌려주면, 굳이 부모를 타고 가지 않아도 이미 부모에서 뿌려준 값이 있기 때문에 상수 시간에 판정이 가능하다. 

1. Failure function을 계산하는 것

Failure function을 계산하는 것은 너비 우선 탐색을 통해서 할 수 있다. KMP랑 비슷한 방법인데, 루트에서의 깊이가 1인 노드들은 failure function이 자명하다 (루트). BFS를 하면 깊이 순으로 트리를 탐색할 수 있다. 루트에서의 깊이가 2인 노드들, 3인 노드들을 순서대로 탐색한다면, 해당 노드보다 깊이가 낮은 노드들은 이미 다 계산이 완료되어 있기 때문에 failure function을 계산할 수 있다. 고로, 부모의 failure function을 안다면 이를 토대로 새로운 failure function을 계산할 수 있다.

이 과정에서 BFS를 사용하기 때문에, 여기서 한 줄의 코드를 추가하는 것만으로도 output check 데이터를 뿌려줄 수 있다. 고로 위에서 output check를 따로 코딩해야 하는 번거로움이 사라진다.

코드 : https://gist.github.com/koosaga/96e5de4ccb99616f9bc3a760ec964cbe

연습 문제가 여러개 있다. 

https://www.acmicpc.net/problem/9250

https://www.acmicpc.net/problem/10256

https://www.acmicpc.net/problem/5905

KMP에서 얘기했듯이 아호 코라식 역시 일종의 유한 상태 오토마타를 만든다. DP 상태에 트라이 노드를 넣으면 된다

http://codeforces.com/contest/163/problem/E

output check가 동적으로 바뀌는 문제이다. 이 경우에는 전처리가 힘드니 루트를 일일히 뒤져보는 것을 생각해보면, 결국 트리에서 쿼리를 하는 문제가 되는데 

 * 쿼리 1 : 노드를 마킹하거나 마킹 해제

 * 쿼리 2 : 해당 노드의 조상들 중 마킹된 노드가 있는지 판별

자료 구조를 사용해서 해결하면 된다.

도움이 될 수 있는 다른 글도 소개한다 : http://blog.myungwoo.kr/101