알고리즘 문제 해결 전략 2 6장 트리 (9)

26.4 트라이를 이용한 다중 문자열 검색

트라이에 포함된 문자열들이 접두사를 공유할 경우, 이 접두사들은 같은 노드에 대응된다는 점을 이용해 탐색 공간을 줄이는 알고리즘을 설계할 수 있음. KMP 알고리즘은 전처리 과정에서 부분 매치 테이블을 계산하는데, 이것은 바늘 문자열의 각 접두사마다 이 접두사의 접두사도 되고 접미사도 되는 문자열의 최대 길이를 계산해 둔 것임. 대응에 실패했을 때 어디로 가서 검색을 계속해야 할지 알려준다는 의미에서 이와 같은 정보를 실패함수라고도 부름. 아호 코라식 알고리즘은 문자열 검색 알고리즘이라고 부름. 아호-코라식 알고리즘은 긴 문서에서 많은 문자열을 동시에 찾아야 하는 검색 엔진 등에서 특히 유용하게 사용됨. 

 

실패 함수의 계산

HARD