public class SuffixTreeNode
private SuffixTreeNode[] _Children = new SuffixTreeNode[256];
public SuffixTreeNode[] Children {
public SuffixTreeNode SuffixLink { get; set; }
public int Start { get; set; }
public int[] End { get; set; }
public int SuffixIndex { get; set; }
for (int i = 0; i < 256; i++)
private static char[] text;
private static SuffixTreeNode root;
private static SuffixTreeNode lastNewNode;
private static SuffixTreeNode activeNode;
private static int count;
private static int activeEdge = -1;
private static int activeLength = 0;
private static int remainingSuffixCount = 0;
private static int leafEnd = -1;
private static int[] rootEnd;
private static int[] splitEnd;
private static int size = -1;
public static SuffixTreeNode NewNode(int start, int[] end)
var node = new SuffixTreeNode
public static int EdgeLength(SuffixTreeNode n)
return n.End[0] - n.Start + 1;
public static bool WalkDown(SuffixTreeNode currNode)
if (activeLength >= EdgeLength(currNode))
activeEdge = text[size - remainingSuffixCount + 1] - ' ';
activeLength -= EdgeLength(currNode);
public static void ExtendSuffixTree(int pos)
while (remainingSuffixCount > 0)
activeEdge = text[pos] - ' ';
if (activeNode.Children[activeEdge] == null)
activeNode.Children[activeEdge] = NewNode(pos, new int[] { leafEnd });
lastNewNode.SuffixLink = activeNode;
var next = activeNode.Children[activeEdge];
if (text[next.Start + activeLength] == text[pos])
if (lastNewNode != null && activeNode != root)
lastNewNode.SuffixLink = activeNode;
splitEnd = new int[] { next.Start + activeLength - 1 };
var split = NewNode(next.Start, splitEnd);
activeNode.Children[activeEdge] = split;
split.Children[activeEdge] - ' ' = NewNode(pos, new int[] { leafEnd });
next.Start += activeLength;
split.Children[activeEdge] = next;
lastNewNode.SuffixLink = split;
if (activeNode == root && activeLength > 0)
activeEdge = text[pos - remainingSuffixCount + 1] - ' ';
else if (activeNode != root)
activeNode = activeNode.SuffixLink;
public static void Print(int i, int j)
for (int k = i; k <= j; k++)
public static void SetSuffixIndexByDFS(SuffixTreeNode n, int labelHeight)
Print(n.Start, n.End[0]);
for (int i = 0; i < 256; i++)
if (n.Children[i] != null)
if (leaf == 1 && n.Start != -1)
Console.WriteLine(" [" + n.SuffixIndex + "]");
SetSuffixIndexByDFS(n.Children[i], labelHeight + EdgeLength(n.Children[i]));
n.SuffixIndex = size - labelHeight;
Console.WriteLine(" [" + n.SuffixIndex + "]");
public static void FreeSuffixTreeByPostOrder(SuffixTreeNode n)
for (int i = 0; i < 256; i++)
if (n.Children[i] != null)
FreeSuffixTreeByPostOrder(n.Children[i]);
public static void BuildSuffixTree(char[] s )
root = NewNode(-1, rootEnd);
for (int i = 0; i < size; i++)
SetSuffixIndexByDFS(root, labelHeight);
FreeSuffixTreeByPostOrder(root);
public static void Main()
char[] text = "abbc".ToCharArray();
Console.WriteLine("Number of nodes in suffix tree are " + count);