접미어 트리의 접미사 링크는 aho-corasick 자동 완성의 실패 에지와 동일합니까?

Question

그렇다면 정확한 문자열 일치를 위해 접미어 트리에서 접미사 링크의 목적을 설명 할 수 있습니까?

Answer 1

아무 것도 없습니다. 접미어 링크는 접미어 트리의 특정 전환입니다. 0 < 함께 문자열 (들 _I)를 나타내는 트리의 주어진 상태 나 < N,이 상태에서 접미사 트리 ( _{난 + 1} S) < 0 문자열을 나타내는 상태로 이끌 I < (n-1)이다.

이러한 특정 전환은 새 문자를 추가하는 동안 트리의 분기를 빠르게 업데이트하기 위해 트리를 구성하는 동안 사용됩니다. 그 이름에서 알 수 있듯이 S 문자열을 나타내는 시작 상태가 주어진 이므로 접미사 링크를 계속 따라 간다면 S의 접미어가 열거됩니다.

그리고 ... 그게 전부입니다. 이 정보를 사용하여 일부 쿼리를 빠르게 수행 할 수 있지만 정확한 문자열 일치와의 관련성은 없습니다.

정확한 문자열 일치가 접미어 트리에서 어떻게 작동합니까? 당신은 당신의 나무 아래를 걷습니다. 노드에 있다면 문자열과 일치하는 문자부터 시작하여 좋은 전환을 선택해야합니다. 불일치가 없으면 명시 적 상태 (노드) 또는 암시 적 상태 (전환 도중에 있음)로 끝날 수 있습니다.이 시점에서 입력 문자열은 접미어로 표시된 문자열의 하위 문자열입니다. 나무.