목록2026/03/16 (1)
Elevation
문자열 - 아호-코라식
아호-코라식(Aho-Corasick) 알고리즘은 다중 문자열 서칭, 즉 하나의 문자열 $T$ 내에서 여러 개의 패턴 문자열 $P_1, P_2, \cdots, P_k$를 찾아야 하는 과제에서 사용 가능한 강력한 알고리즘이다. 아이디어는 매우 직관적이며 단순한데, 찾아야 하는 패턴 문자열들로 트라이(trie)를 만들고, 트라이 내에서 KMP를 수행하는 것이다. 다만 트라이와 kmp 둘 다 다소 복잡한 구조의 알고리즘이다 보니 구현이 간단한 편은 아니다. KMP의 핵심인 실패 함수가 트라이 위에서 어떻게 동작하는지를 이해하는 것이 아호-코라식의 핵심이라고 할 수 있다. 실패 함수의 구성KMP의 작동 원리를 다시 떠올려 보자. $j-1$까지 일치하다가 $j$에서 불일치하는 경우, $j := fail[j-1]$..
ps/기타
2026. 3. 16. 23:02