PS/알고리즘 & 자료구조 썸네일형 리스트형 Aho–Corasick algorithm Aho–Corasick 알고리즘은 특정 문자열에 패턴이 존재하는지를 확인하는 알고리즘이다. 패턴들의 길이의 합을 $m$, 확인하고 싶은 문자열을 $n$이라고 하면 $O(n+m)$의 시간에 패턴이 존재하는지 확인할 수 있다. 자세한 설명은 www.slideshare.net/ssuser81b91b/ahocorasick-algorithm를 참고하자. class AhoCorasick { private: struct node { node* child[26]{}; node* failure = nullptr; node* output = nullptr; } root; void deallocate(node* p) { for (auto q : p -> child) { if (q) { deallocate(q); } } de.. 더보기 Hopcroft–Karp bipartite matching algorithm Hopcroft–Karp 알고리즘은 이분 그래프에서 최대 매칭을 $O((V+E)\sqrt{V})$에 구하는 알고리즘이다. 아이디어는 다음과 같다. 정점의 집합 $X$, $Y$가 있고, 이분그래프 $G = (X \cup Y, E)$의 어떤 매칭 $M$이 있다고 하자. (매칭은 간선의 집합이라고 보고, 자명히 $M \subset E$ 다.) 이때 $X$에 속하면서 아직 매칭되지 않은 정점에서 출발해, $E-M$에 속한 간선과 $M$에 속한 간선을 번갈아 가면서 $Y$에 속하면서 아직 매칭되지 않은 정점으로 도착하는 단순 경로를 확장 경로(augmenting path)라고 한다. 이때 어떤 매칭인지 언급해야 할 필요가 있을 경우 M-확장 경로(augmenting path with respect to M)라고 .. 더보기 이전 1 다음
