우리가 접두어 트리 (trie)를 사용하여 가장 긴 공통 부분 문자열을 찾는 이유는 무엇입니까?

Question

최근 트리를 사용하여 가장 긴 공통 부분 문자열 문제를 해결하는 방법을 배우고 있습니다. Wiki 및 기타 온라인 리소스를 통해 배우면 접미사 트리를 사용하여 가장 긴 공통 부분 문자열을 찾아야합니다. 위키로

는 말했다 :

문자열의 집합의 가장 긴 일반적인 문자열

가 잎 노드가 가장 깊은 내부 노드를 문자열에 대한 일반화 된 접미사 트리를 구축하고 을 찾는 찾을 수 있습니다 Justin로

아래의 하위 트리에있는 모든 문자열 에서 말했다 :

String = ABCDE$XABCZ$ 
    End of word character 1 = $ 
    └── (0) 
     ├── (20) $ 
     ├── (22) ABC 
     │ ├── (15) DE$ 
     │ └── (23) Z$ 
     ├── (24) BC 
     │ ├── (16) DE$ 
     │ └── (25) Z$ 
     ├── (26) C 
     │ ├── (17) DE$ 
     │ └── (27) Z$ 
     ├── (18) DE$ 
     ├── (19) E$ 
     ├── (21) XABCZ$ 
     └── (28) Z$ 

접미사 트리에서는 모든 문자열에서 리프 노드가있는 가장 깊은 내부 노드를 찾아야합니다. 같은 깊이에 여러 개의 노드가있는 경우 해당 노드가 나타내는 문자열의 길이를 비교해야합니다. 즉 ABC, BC 및 C는 모두 동일한 깊이이므로 ABC, BC 및 C 문자열의 길이를 비교하여 어느 것이 더 길어야하는지 비교해야합니다. 분명히 ABC 다.

모든 문자열에서 리프 노드가있는 가장 깊은 내부 노드를 찾는 과정은 실제로 모든 문자열의 모든 접미사 중에서 가장 긴 공통 접두사를 찾는 과정입니다.

여기에 질문이 있습니다. 모든 문자열에서 모든 접미사를 저장하는 접두사 트리를 만드는 이유는 무엇입니까? 그런 다음 접미사 트리를 검색하여이 접미사 중 가장 긴 공통 접두어를 찾을 수 있습니다. 나는이 둘의 차이점을 말할 수 없다. 아무도 내게이 문제를 해결하기 위해 접미사 트리 대신 접미어 트리를 사용하는 몇 가지 실마리를 줄 수 있습니까?

Answer 1

접미어 트리는 길이가 N 인 문자열의 경우에만 O(N) 시간과 공백이 필요합니다. 그래서 그것을 사용하여 선형 시간에 가장 긴 공통 부분 문자열 문제를 해결할 수 있습니다.
문자열의 모든 충분을 트리에 추가하면 최악의 경우시 간과 공간이 O(N^2)이됩니다.

그래서 모든 문자열의 충분 항목을 트라이에 추가한다는 아이디어는 실제로 정확하지만 접미어 트리가있는 솔루션과 비교하면 비효율적입니다.

Answer 2

사전은 사전에 사용됩니다. 접미사는 저장하지 않습니다.