Suffix Tree

Data Structure - Suffix Tree

Introduction

Suffix Tree is a compressed trie containing all the suffixes of the given text T as their keys and positions in the text as their values. [4]

Suffix tree of the text T can be built in the time linear to the length of T. See algorithms of Ukkonen[1] or Weiner[5].

Example of the Suffix Tree built using Ukkonen's algorithm from a word "BANANA".

Suffix tree can be used to efficiently perform the following operations:

  • Find all occurrences of a string P (pattern) in a text T
  • Finding the longest common substring

Suffix tree is closely related to the following data structures:

Implementation

C# implementation:

The code can be tested on Ideone platform. The input text is transformed to the DOT notation and can be rendered using Webgraphviz

Problems

Links

Last updated: 27.04.2018,
created: 21.03.2018.