[알고리즘] Aho-Corasick 아호코라식 (소스 코드)

1. 아호코라식이란?* Aho-Corasick : text(문자열)에서 다수의 pattern(문자열)을 찾는 알고리즘* text의 길이를 tLen, 각 pattern의 길이를 pLen[i], pattern의 개수를 n이라고 할 때,시간복잡도는 O(tLen + pLen[1] + pLen[2] + ...pLen[n])이다.* 다수의 pattern들을 Trie에 저장한뒤, text에서 Trie에 존재하는 pattern을 찾는다.2. 알고리즘 작동 과정i) 주어진 모든 pattern들을 트라이에 저장을 한다.ii) Trie의 실패함수를 생성 (kmp의 실패함수와 비슷한 역할)kmp의 실패함수와 매우 비슷하게 작동을 합니다.iii) Text내의 Pattern 찾기3. 소스 코드1) 트라이의 output을 bool로 구현 : text내에 patte..........

원문링크 : [알고리즘] Aho-Corasick 아호코라식 (소스 코드)