using System;

​

public class SuffixTreeNode {

    public SuffixTreeNode[] Children { get; }

    = new SuffixTreeNode[256]; // Assuming ASCII characters

    public SuffixTreeNode SuffixLink

    {

        get;

        set;

    }

    public int Start

    {

        get;

        set;

    }

    public int[] End

    {

        get;

        set;

    }

    public int SuffixIndex

    {

        get;

        set;

    }

​

    public SuffixTreeNode()

    {

        for (int i = 0; i < 256; i++) {

            Children[i] = null;

        }

​

        SuffixLink = null;

        Start = 0;

        End = new int[1];

        SuffixIndex = -1;

    }

}

​

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,

                                         int[] end)

    {

        count++;

        var node

            = new SuffixTreeNode{ SuffixLink = root,

                                  Start = start, End = end,

                                  SuffixIndex = -1 };

        return node;

    }

​

    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);

            activeNode = currNode;

            return true;

        }

        return false;

    }

​

    public static void ExtendSuffixTree(int pos)

    {

        leafEnd = pos;

        remainingSuffixCount++;

        lastNewNode = null;

​

        while (remainingSuffixCount > 0) {

            if (activeLength == 0) {

                activeEdge = text[pos] - ' ';

            }

​

            if (activeNode.Children[activeEdge] == null) {

                activeNode.Children[activeEdge]

                    = NewNode(pos, new int[] { leafEnd });

​

                if (lastNewNode != null) {

                    lastNewNode.SuffixLink = activeNode;

                    lastNewNode = null;

                }

            }

            else {

                var next = activeNode.Children[activeEdge];

                if (WalkDown(next)) {

                    continue;

                }

​

                if (text[next.Start + activeLength]

                    == text[pos]) {

                    if (lastNewNode != null

                        && activeNode != root) {

                        lastNewNode.SuffixLink = activeNode;

                        lastNewNode = null;

                    }

​

                    activeLength++;

                    break;

                }

​

                splitEnd = new int[] { next.Start

                                       + activeLength - 1 };

                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] - ' ']

                    = next;

​

                if (lastNewNode != null) {

                    lastNewNode.SuffixLink = split;

                }

​

                lastNewNode = split;

            }

​

            remainingSuffixCount--;

            if (activeNode == root && activeLength > 0) {

                activeLength--;

                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++) {

            Console.Write(text[k]);

        }

    }

​

    public static void SetSuffixIndexByDFS(SuffixTreeNode n,

                                           int labelHeight)

    {

        if (n == null)

            return;

​

        if (n.Start != -1) {

            Print(n.Start, n.End[0]);

        }

​

        int leaf = 1;

        for (int i = 0; i < 256; i++) {

            if (n.Children[i] != null) {

                if (leaf == 1 && n.Start != -1) {

                    Console.WriteLine(" [" + n.SuffixIndex

                                      + "]");

                }

​

                leaf = 0;

                SetSuffixIndexByDFS(

                    n.Children[i],

                    labelHeight

                        + EdgeLength(n.Children[i]));

            }

        }

        if (leaf == 1) {

            n.SuffixIndex = size - labelHeight;

            Console.WriteLine(" [" + n.SuffixIndex + "]");

        }

    }

​

    public static void

    FreeSuffixTreeByPostOrder(SuffixTreeNode n)

    {

        if (n == null)

            return;

​

        for (int i = 0; i < 256; i++) {

            if (n.Children[i] != null) {

                FreeSuffixTreeByPostOrder(n.Children[i]);

            }

        }

​

        if (n.SuffixIndex == -1) {

            n.End = null;

        }

    }

​

    public static void BuildSuffixTree()

    {

        size = text.Length;

        rootEnd = new int[1];

        rootEnd[0] = -1;

​

        root = NewNode(-1, rootEnd);

​

        activeNode = root;

        for (int i = 0; i < size; i++) {

            ExtendSuffixTree(i);

        }

        int labelHeight = 0;

        SetSuffixIndexByDFS(root, labelHeight);

​

        FreeSuffixTreeByPostOrder(root);

    }

​

    public static void Main(string[] args)

    {

        text = "abbc".ToCharArray();

        BuildSuffixTree();

        Console.WriteLine(

            "Number of nodes in suffix tree are " + count);

    }

}

​