hellogaon

아호-코라식(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번만 본 뒤 계산을 합니다.그렇기에 이는 긴 문자열에서 많은 문자열을 찾아야 할 경우 사용하면 효율적인 알고리즘입니다.아호-코라식 알고리즘은 아래와 같은 정보들을 추가적으로 ..