Trie

먼저 Suffix trie를 알기 전에 trie를 먼저 알아보자.

trie는 아래와 같은 특징을 지니고 있다.

• 문자 검색을 위해 사용
  
• 빠른 패턴 매칭을 위해 문자열 트리를 기반으로하는 data structure로 저장

trie는 standard trie, suffix trie가 있다.

standard trie는 정확하게 문자를 알아야 검색 할 수 있다.

suffix trie는 임의의 문자만 알아도 검색 할 수 있다.

suffix trie는 suffix tree 혹은 position tree라고도 불린다.

위의 문자열 minimize를 suffix trie로 바꾸어보자.

먼저 왼쪽의 문자열 트리처럼 앞에 한글자씩 지우면서 문자열을 나열한다.

그렇게 나열한 문자열을 살펴보면 mi, i 처럼 중복되는 문자열이 존재하고 nimize, ze, e처럼 하나밖에 없는 문자열이 존재한다.

이렇게 나눈 문자열로 트리를 그리면 아래처럼 된다.