아호-코라식

아호-코라식(Aho-Corasick)은 다중 문자열 검색을 하게 해주는 알고리즘입니다.

이전의 KMP 알고리즘에서 길이가 N인 문자열에서 길이가 M인 문자열 하나를 검색하는 데의 시간복잡도가 O(N + M) 였기에

길이가 N인 문자열에서 길이가 각각 m1, m2, m3...인 문자열 여러 개를 검색할 경우

이에 대한 시간 복잡도는 O(N + m1 + N + m2 + N + m3...)입니다.

이 때 아호-코라식 알고리즘은 이를 P는 검색할 문자열의 출현 횟수 일 때

O(N + m1 + m2 + m3... + P)와 같은 시간 복잡도로 N을 1번만 본 뒤 계산을 합니다.

그렇기에 이는 긴 문자열에서 많은 문자열을 찾아야 할 경우 사용하면 효율적인 알고리즘입니다.

아호-코라식 알고리즘은 아래와 같은 정보들을 추가적으로 가지고 있는 트라이를 이용합니다.

1. fail : 이 노드에서 매칭이 실패했을 때 다음으로 가서 시도해야할 노드의 포인터

2. output : 각 노드에 도달했을 때 어떤 문자열들을 발견하게 되는지를 저장

KMP 알고리즘의 부분 일치 테이블의 역할을 fail이라는 포인터가 하며

트라이의 종료노드에 도달했을 때에는 output에 있는 정보를 활용하여 검색 된 문자열을 알려주는 알고리즘입니다.

기본 문제

9250번: 문자열 집합 판별