Compiler Club의 설명은 여러 문자열의 공통 접두사를 트라이로 묶은 뒤 접미사 링크를 더해 Aho-Corasick 자동자를 만드는 과정을 다룬다. 다음 문자가 맞지 않아도 가능한 가장 긴 접미사 상태로 옮겨 여러 패턴을 동시에 찾는다. 관련 알고리즘 설명에서도 탐색 비용은 입력 길이뿐 아니라 출력되는 일치 건수를 포함한다고 확인했다. 겹치는 패턴이 많으면 결과 자체가 커지므로 단순히 데이터 크기와 무관하게 빠른 검색으로 이해하면 안 된다.
Tech로 돌아가기
Tech
Aho-Corasick, 여러 문자열을 한 번에 찾는 구조
다중 패턴 검색은 접두사 트라이와 실패 링크를 결합하면 같은 입력을 되짚는 낭비를 줄일 수 있다.