SuffixTree | C# Online Compiler

SuffixTree by foxandfiddle

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

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

'Wednesday, 19-Apr-23' found at index 0.
'Wednesday, 19-Apr-23' found at index 40.
'Wed, 19 Apr 2023' found at index 80.
'Wed, 19 Apr 23' found at index 120.
'Wed, 19 Apr 2023' found at index 159.
'Wednesday, 19-Apr-2023' found at index 200.
'Wed, 19 Apr 23' found at index 244.
'Wed, 19 Apr 2023' found at index 280.
'31th December 2024' found at index 331.
'2024 November 18' found at index 729.
'2024 November 18' found at index 1114.
'Wed, 19 Apr 2023' found at index 1191.
'Wednesday, 19-Apr-23' found at index 1229.
'Wed, 19 Apr 23' found at index 1269.
'Wed, 19 Apr 2023' found at index 1305.
'Wed, 19 Apr 23' found at index 1343.
'Wednesday, 19-Apr-2023' found at index 1443.
'Wed, 19 Apr 2023' found at index 1486.

Cached Result
Last Run:	9:45:02 am
Compile:	0.101s
Execute:	0.15s
Memory:	0b
CPU:	0.251s

View IL Code