using System;

​

public class SuffixTreeNode 

{ 

    private SuffixTreeNode[] _Children = new SuffixTreeNode[256]; 

    public SuffixTreeNode[] Children { 

        get; 

        set; 

    }  

// 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[activeEdge] - ' ' = NewNode(pos, new int[] { leafEnd }); 

                next.Start += activeLength; 

                split.Children[activeEdge] = 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(char[] s ) 

    { 

//      text = s; 

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

    {

        char[] text = "abbc".ToCharArray(); 

        BuildSuffixTree(text); 

        Console.WriteLine("Number of nodes in suffix tree are " + count); 

    }

} 

​

​

​

​

​