Ukkonen’s Suffix Tree Construction | C# Online Compiler

Ukkonen’s Suffix Tree Construction by foxandfiddle

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

​x
 
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); 
    }
} 
​
​
​
​
​

The reverse of the string is:
gnirts ruoy

Cached Result
Last Run:	5:20:40 pm
Compile:	0.106s
Execute:	0s
Memory:	0b
CPU:	0.016s

View IL Code