Aho-Corasick(AC)[아호코라식] Algorithm

AC 알고리즘은 주어진 텍스트에서 여러 패턴을 동시에 찾는데 사용되는 알고리즘

 Process

1. Prefix Tree (Trie) 생성 - 이 단계에서는 주어진 모든 패턴 집합 P에 대한 Prefix Tree (또는 Trie)를 구축합니다. 각 노드는 고유한 문자 라벨을 가지며, 루트에서 특정 노드까지의 경로는 해당 노드에 도달하는 데 사용된 문자열을 나타냅니다. 트리의 모든 노드는 Q에 속하며, 루트 노드는 q0으로 표시됩니다.
2. Accepting States 표시 - 각 패턴 문자열이 Trie에서 끝나는 노드는 "Accepting" 또는 "Output" 상태로 표시됩니다. 이는 해당 노드가 패턴 문자열의 끝을 나타내기 때문입니다.
3. goto 함수 생성 - goto 함수는 주어진 현재 상태와 입력 문자에 대한 다음 상태를 정의합니다. 이 함수는 Trie를 구축하는 동안 생성되며, 각 노드 (상태)에 대해 해당 노드에서 시작하는 모든 직접적인 자식 노드 (상태)에 대한 매핑을 포함합니다.
4. failure 함수 생성 - failure 함수는 알고리즘이 패턴과 일치하지 않을 때 "되돌아갈" 상태를 결정하는 데 사용됩니다. 이 함수는 각 노드에서 가장 긴 접미사에 대한 다음 상태를 제공합니다. 이 접미사는 또한 다른 패턴의 접두사이어야 합니다. failure 함수는 BFS (Breadth-First Search) 알고리즘을 사용하여 Trie에 대해 계산됩니다.