(Stankonia, 2000)
https://www.slideshare.net/ssuser81b91b/ahocorasick-algorithm 문자열 S와 여러 개의 문자열 T가 주어졌을 때, T에 있는 문자열 중 하나와 S가 매칭이 되는 지를 계산 할 수 있는 알고리즘이다. 선형 시간에 작동한다.Aho Corasick Algorithm을 알기 위해서는 KMP 알고리즘과 트라이에 대한 이해가 필요하다. KMP 알고리즘에 대한 koosaga.com의 설명 아호 코라식 알고리즘을 한 문장으로 설명하면, KMP에서 사용하는 Failure function을 트라이에 확장시키는 것. 딱 이것으로 끝난다. 스텝도 비슷하다. * 1. 트라이가 주어졌을 때 트라이에서 Failure function (Failure link나 Suffix link라고도..
문자열 S와 T가 주어졌을 때, S의 부분 문자열 중 T가 몇번 등장하는 지를 찾는 문제를 생각해보자. 예를 들어 "koosaga" 에서 "saga" 를 찾으면 "koos" != "saga", "oosa" != "saga", "osag" != "saga", "saga" == "saga" 여서 총 한번 등장하고, "aa" 를 찾으면 "ko" != "aa", "oo" != "aa", "os" != "aa", "sa" != "aa", "ag" != "aa", "ga" != "aa" 여서 단 한번도 등장하지 않는다. N = (S의 길이), M = (T의 길이) 라 하자. S[i, j] = (i번째 문자에서 j-1번째 문자까지를 포함하는 부분 문자열) 이라고 하자. 예를 들어 "koosaga"[0, 3] = "k..
- Total
- Today
- Yesterday