Skip to content

A C++ implementation of a Generalized Suffix Tree using Ukkonen's algorithm

Notifications You must be signed in to change notification settings

atuljangra/Ukkonen-SuffixTree

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

24 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Implementation of Ukkonen's algorithm in C++. This is very special algorithm. You may have a look at the original paper here: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf.

Do |make| to compile and |make run| to execute.

Output would be all the edges in the suffix tree with the following details: StartNode Endnode SuffixlinkOfEndNode StartLabelIndex EndLabelIndex String

where: StartLabelIndex is the starting index of the substring represented by this edge. EndLabelIndex is the ending index of the substring represented by this edge. String is the full label represented by this edge.

Alphabet set is unlimited.

To get the explicit suffix tree you have to end the input string with a unique character.

You can do a search in the suffix tree for any substring.

This is a linear time algorithm.

Only significant data structure that I've used is a hash table. This implementaion of hash table has an constant average case complexity.

About

A C++ implementation of a Generalized Suffix Tree using Ukkonen's algorithm

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages