README.md

[baekjoon-9250] 문자열 집합 판별

아호-코라식 (Aho-Corasick) 알고리즘

아호코라식(Aho-Corasick)

이젠 트라이 코드가 제법 익숙해졌는지, 문자열 검색 문제인 것을 알자마자 신나게 트라이를 구현해 풀었는데, 시간 초과 및 틀렸습니다 결과를 보게 되었다. 찾아보니 이 문제는 아호-코라식 알고리즘을 이용해 풀어야 하는 것이었다.

["he", "his", "she"] 의 문자열 집합이 주어졌을 때, shis 문자열에는 his가 포함되어 있으나, 단순히 트라이를 이용해 문제를 풀려고 하면 s, h를 지나고 i가 나왔을 때 검색을 중단하여 잘못된 결과를 낼 수 있다.

아호-코라식 알고리즘은 fail 이라는 포인터를 통해 검색에 실패했을 때 검색할 수 있는 다른 경로를 찾아 탐색하도록 되어 있다. 이는 위 블로그에 매우 잘 설명되어 있다. 이해하는데 시간이 매우 오래걸렸지만, 코드를 보고 직접 그림을 그려 따라가다 보니 이해할 수 있었다.

실행 시간이 적어서 놀랐다 !! (장장 3시간에 걸친 힘든 이해의 과정이었다...)