Posted on by Kalkicode
Code Tree

suffix tree implementation in java

Java program for suffix tree implementation. Here more information.

// Java program for
// Suffix tree implementation
import java.util.ArrayList;
class TreeNode
{
    public String sub ;
    public ArrayList < Integer > child;
    public TreeNode()
    {
        this.sub = "";
        this.child = new ArrayList < Integer > ();
    }
}
public class SuffixTree
{
    public ArrayList < TreeNode > nodes;
    public SuffixTree(String data)
    {
        this.nodes = new ArrayList < TreeNode > ();
        this.nodes.add(new TreeNode());
        // Construct tree
        this.buildTree(data);
    }
    public void addSuffix(String suf)
    {
        // Declare some useful auxiliary variables
        int n = 0;
        int i = 0;
        int x2 = 0;
        int n2 = 0;
        int n3 = 0;
        int j = 0;
        TreeNode temp = null;
        boolean process = true;
        String sub2 = "";
        while (i < suf.length())
        {
            char b = suf.charAt(i);
            ArrayList < Integer > children = this.nodes.get(n).child;
            while (process)
            {
                if (x2 == children.size())
                {
                    n2 = this.nodes.size();
                    temp = new TreeNode();
                    temp.sub = suf.substring(i);
                    this.nodes.add(temp);
                    children.add(n2);
                    return;
                }
                n2 = children.get(x2);
                if (this.nodes.get(n2).sub.charAt(0) == b)
                {
                    process = false;
                }
                else
                {
                    x2++;
                }
            }
            sub2 = this.nodes.get(n2).sub;
            process = true;
            while (j < sub2.length() && (i + j) < suf.length() && process == true)
            {
                if (suf.charAt(i + j) != sub2.charAt(j))
                {
                    n3 = n2;
                    n2 = this.nodes.size();
                    temp = new TreeNode();
                    temp.sub = sub2.substring(0, j);
                    temp.child.add(n3);
                    this.nodes.add(temp);
                    this.nodes.get(n3).sub = sub2.substring(j);
                    this.nodes.get(n).child.set(x2, n2);
                    process = false;
                }
                else
                {
                    j++;
                }
            }
            i += j;
            n = n2;
            // Reset value
            x2 = 0;
            n2 = 0;
            n3 = 0;
            j = 0;
            temp = null;
            process = true;
            sub2 = "";
        }
    }
    public void buildTree(String str)
    {
        for (int i = 0; i < str.length(); ++i)
        {
            addSuffix(str.substring(i));
        }
    }
    public void printData(int n, String prefix)
    {
        ArrayList < Integer > children = this.nodes.get(n).child;
        if (children.isEmpty())
        {
            System.out.println("⤑ " + this.nodes.get(n).sub);
            return;
        }
        System.out.println("┐ " + this.nodes.get(n).sub);
        for (int i = 0; i < children.size() - 1; i++)
        {
            int c = children.get(i);
            System.out.print(prefix + "├─");
            printData(c, prefix + "│ ");
        }
        System.out.print(prefix + "└─");
        printData(children.get(children.size() - 1), prefix + "  ");
    }
    public void visualize()
    {
        if (this.nodes.isEmpty())
        {
            System.out.print("\nEmpty Tree");
            return;
        }
        printData(0, "");
    }
    public static void main(String[] args)
    {
        // Create Suffix Tree
        SuffixTree tree1 = new SuffixTree("coconut");
        SuffixTree tree2 = new SuffixTree("BAABAIAIIBI");
        // Print path
        tree1.visualize();
        tree2.visualize();
    }
}

Output

┐
├─┐ co
│ ├─⤑ conut
│ └─⤑ nut
├─┐ o
│ ├─⤑ conut
│ └─⤑ nut
├─⤑ nut
├─⤑ ut
└─⤑ t
┐
├─┐ B
│ ├─┐ A
│ │ ├─⤑ ABAIAIIBI
│ │ └─⤑ IAIIBI
│ └─⤑ I
├─┐ A
│ ├─⤑ ABAIAIIBI
│ ├─⤑ BAIAIIBI
│ └─┐ I
│   ├─⤑ AIIBI
│   └─⤑ IBI
└─┐ I
  ├─⤑ AIIBI
  ├─⤑ IBI
  └─⤑ BI

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment