알고리즘1 Acho-Corasick 알고리즘 Aho-Corasick 알고리즘이란?Aho-Corasick 알고리즘은 문자열 검색 알고리즘으로, 여러개의 패턴을 동시에 검색하는데 사용됩니다.알고리즘을 이용하면 O(m+n+k)의 시간 복잡도로 패턴 집합에 대하여 패턴 길이와 텍스트의 선형 시간에 탐색을 처리할 수 있습니다(m: 모든 패턴의 길이 합, n: 텍스트 크기, k: 텍스트 내에 패턴의 발생 수). 알고리즘의 구성● 키워드 트리패턴의 글자 하나하나를 간선으로 한다. 서로 패턴들의 접두사가 최대한 같을 때까지는 같은 정점으로 간선을 따라가고 글자가 달라지면 다른 간선으로 가도록 만든다. ● 실패 링크모든 패턴을 차례로 Keyword Tree에 넣은 이 후에는 이 Tree에 실패 링크(Failure link)를 추가해주게 된다. 루트에서 거리가 1인.. 2024. 5. 16. 이전 1 다음
