Dot Algo∙ DS/알고리즘 개념
2021. 11. 29.
[알고리즘] 다중 문자열 검색 아호 코라식(Aho-Corasick) 알고리즘 정리 (Java)
아호 코라식(Aho-Corasick) 알고리즘 아호 코라식 알고리즘(Aho–Corasick string matching algorithm)은 Alfred V. Aho와 Margaret J. Corasick이 고안한 문자열 검색 알고리즘(매칭 알고리즘)이다. (위키 참고) 패턴 1개를 탐색하는 매칭 알고리즘은 선형 시간에 구현됨을 KMP 등 여러 알고리즘을 통하여 증명되었다. 하지만 패턴 집합에 대하여 이러한 알고리즘을 수행하게 되면 패턴 개수에 비례하여 그 속도가 느려지게 된다. m = 모든 패턴들의 길이 합, p = 패턴수, n = text 크기 즉 , O(m + p*n)의 시간 복잡도를 가지게 된다. 하지만 아호 코라식 알고리즘을 이용하면 O (m + p + n)의 시간복잡도로 패턴 집하에 대하여 패..
![[알고리즘] 다중 문자열 검색 아호 코라식(Aho-Corasick) 알고리즘 정리 (Java)](http://i1.daumcdn.net/thumb/C450x300/?fname=https://blog.kakaocdn.net/dn/cIgyTc/btrmnmomZXE/WoKzasyxP4MKASNNE1mkr1/img.png)