Aho-Corasick 알고리듬

Aho-Corasick은 여러 패턴을 저장한 트라이에 링크를 추가해, 입력 시퀀스에서 여러 부분 문자열을 동시에 찾는 오토마톤을 구성함 접미사 링크는 전이 실패 시 현재 문자열의 접미사이면서 패턴의 접두사인 가장 긴 문자열을 보존해, 해당 상태에서 실패한 문자를 다시 처리하도록 함 출력 링크는 한 패턴을 찾았을 때 그 접미사에 해당하는 다른 패턴도 함께 출력하게 함 접미사 링크와 출력 링크는 너비 우선 탐색으로 계산하며, 먼저 처리한 짧은 문자열의 정보를 더 긴 문자열의 링크 구성에 활용함 링크를 추가한 트라이를 직접 실행할 수도 있지만, 추가 너비 우선 탐색으로 전이와 출력을 미리 확정한 결정적 유한 오토마톤(DFA) 을 구성할 수도 있음 트라이로 패턴 집합 저장하기 트라이(trie) 는 문자열 집합을 저장하는 n진 트리로, 각 간선에는 문자가 붙고 각 노드는 루트에서 해당 노드까지 간선 문자를 이어 붙인 문자열을 나타냄 공통 접두사를 가진 문자열은 같은 경로를 공유해 중복을 줄임 suit, suited, suitable을 저장하면 세 항목이 suit 경로를 공유함 완전한 패턴에 해당하는 노드는 별도로 표시함 접미사 링크로 전이 실패에서 복구하기 접미사 링크(suffix link) 는 현재 노드가 나타내는 문자열의 접미사 중, 트라이에 있는 패턴의 접두사와 일치하는 가장 긴 문자열을 보존함 현재 상태에서 입력 문자를 처리할 간선이 없으면 이 링크를 따라 이동하고, 실패한 문자부터 다시 매칭을 진행함 패턴이 item, suits이고 입력이 suitems이면, suit까지 읽은 상태에서 다음 문자 e를 처리할 간선이 없음 suit 상태의 접미사 링크는 it 상태를 가리킴 이 상태에서 e부터 계속 읽으면 su[item]s처럼 item을 찾을 수 있음 루트에서도 전이할 수 없는 문자는 어떤 패턴의 시작도 될 수 없으므로, 루트에 머문 채 입력 위치만 다음 문자로 이동함 너비 우선 탐색으로 접미사 링크 구성하기 링크 계산은 너비 우선 탐색(BFS) 순서로 진행함 루트와 루트의 바로 아래 자식들은 접미사 링크가 루트를 가리킴 나머지 노드는 부모의 접미사 링크가 가리키는 상태에서 시작해, 현재 노드로 들어오는 문자와 같은 이름의 간선을 찾음 해당 간선이 있으면 그 목적지를 접미사 링크로 사용하고, 없으면 접미사 링크를 계속 따라감 루트까지 왔을 때도 해당 간선이 없으면 루트를 사용하며, 루트의 자기 링크를 무한히 따라가지...