public class SuffixTreeNode {
public SuffixTreeNode[] Children { get; }
= new SuffixTreeNode[256];
public SuffixTreeNode SuffixLink
for (int i = 0; i < 256; i++) {
public class SuffixTree {
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,
= new SuffixTreeNode{ SuffixLink = root,
Start = start, End = end,
public static int EdgeLength(SuffixTreeNode n)
return n.End[0] - n.Start + 1;
public static bool WalkDown(SuffixTreeNode currNode)
if (activeLength >= EdgeLength(currNode)) {
= 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 });
if (lastNewNode != null) {
lastNewNode.SuffixLink = activeNode;
var next = activeNode.Children[activeEdge];
if (text[next.Start + activeLength]
lastNewNode.SuffixLink = activeNode;
splitEnd = new int[] { next.Start
var split = NewNode(next.Start, splitEnd);
activeNode.Children[activeEdge] = split;
split.Children[text[pos] - ' ']
= NewNode(pos, new int[] { leafEnd });
next.Start += activeLength;
split.Children[text[next.Start] - ' ']
if (lastNewNode != null) {
lastNewNode.SuffixLink = split;
if (activeNode == root && activeLength > 0) {
= 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,
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
+ EdgeLength(n.Children[i]));
n.SuffixIndex = size - labelHeight;
Console.WriteLine(" [" + n.SuffixIndex + "]");
FreeSuffixTreeByPostOrder(SuffixTreeNode n)
for (int i = 0; i < 256; i++) {
if (n.Children[i] != null) {
FreeSuffixTreeByPostOrder(n.Children[i]);
if (n.SuffixIndex == -1) {
public static void BuildSuffixTree()
root = NewNode(-1, rootEnd);
for (int i = 0; i < size; i++) {
SetSuffixIndexByDFS(root, labelHeight);
FreeSuffixTreeByPostOrder(root);
public static void Main(string[] args)
text = "abbc".ToCharArray();
"Number of nodes in suffix tree are " + count);