Algorithm. 문자열 - 접미어 트리

1. 접미어 트리

• 하나의 문자열의 모든 접미어들을 포함하는 트라이(Trie)의 압축된 표현
• 문자열 연산에 필요한 알고리즘을 빠르게 구현할 수 있다.
• 응용
  • 문자열 매칭(Exact string matching)
  • 부분 문자열 매칭(Substring matching)
  • 최장 공통 부분 문자열(Longest common substring of 2 strings)

예시)

문자열 S = {xabxac}에 대한 접미어 트리

• 길이가 6이므로 6개의 접미어가 존재
• 단말노드에는 접미어의 시작위치를 저장한다.
• 루트를 제외한 내부 노드는 최소 2개의 자식을 갖는다.
• 각 간선은 문자열 S의 부분문자열 라벨(label)이 부여된다.
• 한 노드에서 나가는 두개의 간선이 같은 문자열 라벨을 가질 수 없다.

• 루트에서 단말노드 i까지 경로에서 존재하는 라벨들을 연결하면 문자열 S의 i위치부터 끝까지의 문자열 S[i ... s]

접미어 트리 속성 정리

$ 문자 추가

• 문자열 S의 끝에 추가한다.
• 종료 문자로 하며 가장 작은 값을 가지는 문자이다.(문자 비교 시)
• 간선에 부여된 라벨을 효과적으로 저장하기 위해 부분 문자열 T[i ... j]의 인덱스 시작과 끝(i, j)을 저장한다.