ahocorasick

Aho-corasick

기본 개념설명은 https://cp-algorithms.com/string/aho_corasick.html 보다 잘할 자신이 없으므로 링크만 걸겠다. 많은 Aho-corasick 구현체가 bfs를 사용한 bottom-up DP를 사용하는데, 이 포스트에서는 Top-down DP방식으로 Aho-corasick을 구현하는것을 다뤄보려고 한다. 링크에서는 output-link 구현에 대한 내용이 빠져있는데, 아호코라식에 대한 이해를 바탕으로 top-down으로 구현을 완성할 수 있었다. Top-down방식으로 짜면 별도의 bfs가 필요하지 않으며, 별도의 dp변수도 필요하지 않다. 그냥 suffix link와 output link자체를 사용해서 memoization이 가능하기 때문에 구현이 훨씬 간결해지며, 재귀적인 로직을 그대로 코드로 옮길 수 있다. 심지어 Online으로 Pattern추가가 가능하다!! 아무튼 이런이유로 잘 알려진 bfs구현체보다 깡DP구현이 훨씬 좋은것 같다.

코드

https://github.com/tuxedcat/ps.cpp/blob/main/incl/str/ahocorasik.h