Are suffix trees and suffix arrays identical? What are the differences

algorithmssuffix-treestheory

I have read some information through internet…i found that somehow suffix tree is quite similar to suffix array but somehow they are no the same thing..

Given a string, a suffix tree construction algorithm looks something like this (I copied the algorithm from a website)

FOR i ← 1 to n-1        
FOR j ← 1 to i+1             
   find the end path for S[j…i]
   extend the path, if needed, to S[i+1]

suffix tree able to list down all the subtring obtained from a given string

However, does the suffix array also give the same functionality to obtain the list of substrings? Or are suffix arrays just an implementation of suffix trees? Or suffix array just provide some storing function?

Best Answer

A suffix array is a space-efficient datastructure, which, if stored together with the original string, provides the same functions as a suffix tree.

So yes, you can think of a suffix array as a storage mechanism for suffix trees. Depending on the details, there may be performance costs to using arrays over full-blown trees, which typically are outweighed by the space-use benefits. I believe the arrays are constructed almost identically to the way trees are constructed, and, in practice, suffix arrays are the preferred method for storing/representing a suffix tree.

Related Solutions

Smallest lexicographical rotation of a string using suffix arrays in O(n)

A simple trick to construct all rotations of a string of length N is to concatenate the string with itself.

Then every N-length substring of this 2N-length string is a rotation of the original string.

Locating the "lexicographically minimal" substring is then done with your O(N) tree construction.

C++ – How to Print Bottom View of a Binary Tree?

First create a list, indexed by vertical line, recording the maximum level found on that line. Walk the tree one time to fill in this list.

At this point every list[vertical] entry contains the level that can be seen in the bottom view of the tree.

Then walk the tree again, printing out each node whose level matches the maximum found on its line.

int MaxLvl[];

void printBotOne( node *qNode, int Level, int Column ) {
  if qNode then {
    printBotOne(qNode->left, Level+1, Column-1);
    if MaxLvl[Column]<Level then MaxLvl[Column] = Level;
    printBotOne(qNode->right, Level+1, Column+1);
  }
}

void printBotTwo( node *qNode, int Level, int Column ) {
  if qNode then {
    printBotTwo(qNode->left, Level+1, Column-1);
    if MaxLvl[Column]==Level then cout << qNode->data << " ";
    printBotTwo(qNode->right, Level+1, Column+1);
  }
}

void printBottom( node *qNode ) {
  for(int II = 0; II<nodecount; II++) MaxLvl[II] = 0;
  printBotOne(qNode, 0, nodecount/2);
  printBotTwo(qNode, 0, nodecount/2);
}

This requires a 1D array and runs in O(N).

Best Answer

Related Solutions

Smallest lexicographical rotation of a string using suffix arrays in O(n)

C++ – How to Print Bottom View of a Binary Tree?

Related Topic