Suffix tree implementation

Here given code implementation process.

// 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
// Include namespace system
using System;
using System.Collections.Generic;
public class TreeNode
{
	public String sub;
	public List < int > child;
	public TreeNode()
	{
		this.sub = "";
		this.child = new List < int > ();
	}
}
public class SuffixTree
{
	public List < TreeNode > nodes;
	public SuffixTree(String data)
	{
		this.nodes = new List < 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[i];
			List < int > children = this.nodes[n].child;
			while (process)
			{
				if (x2 == children.Count)
				{
					n2 = this.nodes.Count;
					temp = new TreeNode();
					temp.sub = suf.Substring(i);
					this.nodes.Add(temp);
					children.Add(n2);
					return;
				}
				n2 = children[x2];
				if (this.nodes[n2].sub[0] == b)
				{
					process = false;
				}
				else
				{
					x2++;
				}
			}
			sub2 = this.nodes[n2].sub;
			process = true;
			while (j < sub2.Length && (i + j) < suf.Length && process == true)
			{
				if (suf[i + j] != sub2[j])
				{
					n3 = n2;
					n2 = this.nodes.Count;
					temp = new TreeNode();
					temp.sub = sub2.Substring(0, j);
					temp.child.Add(n3);
					this.nodes.Add(temp);
					this.nodes[n3].sub = sub2.Substring(j);
					this.nodes[n].child[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)
		{
			this.addSuffix(str.Substring(i));
		}
	}
	public void printData(int n, String prefix)
	{
		List < int > children = this.nodes[n].child;
		if ((children.Count == 0))
		{
			Console.WriteLine("⤑ " + this.nodes[n].sub);
			return;
		}
		Console.WriteLine("┐ " + this.nodes[n].sub);
		for (int i = 0; i < children.Count - 1; i++)
		{
			int c = children[i];
			Console.Write(prefix + "├─");
			this.printData(c, prefix + "│ ");
		}
		Console.Write(prefix + "└─");
		this.printData(children[children.Count - 1], prefix + "  ");
	}
	public void visualize()
	{
		if ((this.nodes.Count == 0))
		{
			Console.Write("\nEmpty Tree");
			return;
		}
		this.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
class TreeNode :
	def __init__(self) :
		self.sub = ""
		self.child = []
	

class SuffixTree :
	def __init__(self, data) :
		self.nodes = []
		self.nodes.append(TreeNode())
		#  Construct tree
		self.buildTree(data)
	
	def addSuffix(self, suf) :
		#  Declare some useful auxiliary variables
		n = 0
		i = 0
		x2 = 0
		n2 = 0
		n3 = 0
		j = 0
		temp = None
		process = True
		sub2 = ""
		while (i < len(suf)) :
			b = suf[i]
			children = self.nodes[n].child
			while (process) :
				if (x2 == len(children)) :
					n2 = len(self.nodes)
					temp = TreeNode()
					temp.sub = suf[i: ]
					self.nodes.append(temp)
					children.append(n2)
					return
				
				n2 = children[x2]
				if (self.nodes[n2].sub[0] == b) :
					process = False
				else :
					x2 += 1
				
			
			sub2 = self.nodes[n2].sub
			process = True
			while (j < len(sub2) and(i + j) < len(suf) and process == True) :
				if (suf[i + j] != sub2[j]) :
					n3 = n2
					n2 = len(self.nodes)
					temp = TreeNode()
					temp.sub = sub2[0: j]
					temp.child.append(n3)
					self.nodes.append(temp)
					self.nodes[n3].sub = sub2[j: ]
					self.nodes[n].child[x2] = n2
					process = False
				else :
					j += 1
				
			
			i += j
			n = n2
			#  Reset value
			x2 = 0
			n2 = 0
			n3 = 0
			j = 0
			temp = None
			process = True
			sub2 = ""
		
	
	def buildTree(self, str) :
		i = 0
		while (i < len(str)) :
			self.addSuffix(str[i: ])
			i += 1
		
	
	def printData(self, n, prefix) :
		children = self.nodes[n].child
		if ((len(children) == 0)) :
			print("⤑ ", self.nodes[n].sub)
			return
		
		print("┐ ", self.nodes[n].sub)
		i = 0
		while (i < len(children) - 1) :
			c = children[i]
			print(prefix ,"├─", end = "")
			self.printData(c, prefix + "│ ")
			i += 1
		
		print(prefix ,"└─", end = "")
		self.printData(children[len(children) - 1], prefix + "  ")
	
	def visualize(self) :
		if ((len(self.nodes) == 0)) :
			print("\nEmpty Tree", end = "")
			return
		
		self.printData(0, "")
	

def main() :
	#  Create Suffix Tree
	tree1 = SuffixTree("coconut")
	tree2 = SuffixTree("BAABAIAIIBI")
	#  Print path
	tree1.visualize()
	tree2.visualize()

if __name__ == "__main__": main()

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
import scala.collection.mutable._;
class TreeNode(var sub: String,
	var child: ArrayBuffer[Int])
{
	def this()
	{
		this("", new ArrayBuffer[Int]());
	}
}
class SuffixTree(var nodes: ArrayBuffer[TreeNode])
{
	def this(data: String)
	{
		this(new ArrayBuffer[TreeNode]());
		this.nodes += new TreeNode();
		// Construct tree
		this.buildTree(data);
	}
	def addSuffix(suf: String): Unit = {
		// Declare some useful auxiliary variables
		var n: Int = 0;
		var i: Int = 0;
		var x2: Int = 0;
		var n2: Int = 0;
		var n3: Int = 0;
		var j: Int = 0;
		var temp: TreeNode = null;
		var process: Boolean = true;
		var sub2: String = "";
		while (i < suf.length())
		{
			var b: Char = suf.charAt(i);
			var children: ArrayBuffer[Int] = this.nodes(n).child;
			while (process)
			{
				if (x2 == children.size)
				{
					n2 = this.nodes.size;
					temp = new TreeNode();
					temp.sub = suf.substring(i);
					this.nodes += temp;
					children += n2;
					return;
				}
				n2 = children(x2);
				if (this.nodes(n2).sub.charAt(0) == b)
				{
					process = false;
				}
				else
				{
					x2 += 1;
				}
			}
			sub2 = this.nodes(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 += n3;
					this.nodes += temp;
					this.nodes(n3).sub = sub2.substring(j);
					this.nodes(n).child(x2) = n2;
					process = false;
				}
				else
				{
					j += 1;
				}
			}
			i += j;
			n = n2;
			// Reset value
			x2 = 0;
			n2 = 0;
			n3 = 0;
			j = 0;
			temp = null;
			process = true;
			sub2 = "";
		}
	}
	def buildTree(str: String): Unit = {
		var i: Int = 0;
		while (i < str.length())
		{
			addSuffix(str.substring(i));
			i += 1;
		}
	}
	def printData(n: Int, prefix: String): Unit = {
		var children: ArrayBuffer[Int] = this.nodes(n).child;
		if ((children.size == 0))
		{
			println("⤑ " + this.nodes(n).sub);
			return;
		}
		println("┐ " + this.nodes(n).sub);
		var i: Int = 0;
		while (i < children.size - 1)
		{
			var c: Int = children(i);
			print(prefix + "├─");
			printData(c, prefix + "│ ");
			i += 1;
		}
		print(prefix + "└─");
		printData(children(children.size - 1), prefix + "  ");
	}
	def visualize(): Unit = {
		if ((this.nodes.size == 0))
		{
			print("\nEmpty Tree");
			return;
		}
		printData(0, "");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// Create Suffix Tree
		var tree1: SuffixTree = new SuffixTree("coconut");
		var tree2: SuffixTree = 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
// Include header file
#include <iostream>
#include <string>
#include <vector>
// C++ program for
// Suffix tree implementation
using namespace std;
class TreeNode
{
    public: string sub;
    vector < int > child; 
    TreeNode()
    {
        this->sub = "";
    }
};
class SuffixTree
{
    public: 
    vector < TreeNode *> nodes;
    SuffixTree(string data)
    {
    
        this->nodes.push_back(new TreeNode());
        // Construct tree
        this->buildTree(data);
    }
    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;
        bool process = true;
        string sub2 = "";
        while (i < suf.length())
        {
            char b = suf[i];

          
            while (process)
            {

                if (x2 == this->nodes[n]->child.size())
                {
                    n2 = this->nodes.size();
                    temp = new TreeNode();
                    temp->sub = suf.substr(i);
                    

                    this->nodes.push_back(temp);
                    this->nodes[n]->child.push_back(n2);
                    return;
                }
                n2 = this->nodes[n]->child.at(x2);
                if (this->nodes.at(n2)->sub[0] == b)
                {
                    process = false;
                }
                else
                {
                    x2++;
                }
            }
            sub2 = this->nodes.at(n2)->sub;
            process = true;
            while (j < sub2.length() && (i + j) < suf.length() && process == true)
            {
                if (suf[i + j] != sub2[j])
                {
                    n3 = n2;
                    n2 = this->nodes.size();
                    temp = new TreeNode();
                    temp->sub = sub2.substr(0, j);
                    temp->child.push_back(n3);
                    this->nodes.push_back(temp);
                    this->nodes.at(n3)->sub = sub2.substr(j);
                    this->nodes.at(n)->child.at(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 = "";

        }
    }
    void buildTree(string str)
    {
        for (int i = 0; i < str.length(); ++i)
        {
            this->addSuffix(str.substr(i));
        }
    }
    void printData(int n, string prefix)
    {
        vector < int > children = this->nodes[n]->child;;
        if (children.empty())
        {
            cout << "⤑ " << this->nodes.at(n)->sub << endl;
            return;
        }
        cout << "┐ " << this->nodes.at(n)->sub << endl;
        for (int i = 0; i < children.size() - 1; i++)
        {
            int c = children.at(i);
            cout << prefix << "├─";
            this->printData(c, prefix  +  "│ ");
        }
        cout << prefix << "└─";
        this->printData(children.at(children.size() - 1), prefix  +  "  ");
    }
    void visualize()
    {
        if (this->nodes.empty())
        {
            cout << "\nEmpty Tree";
            return;
        }
        this->printData(0, "");
    }
};
int main()
{
    // Create Suffix Tree
    SuffixTree *tree1 = new SuffixTree("coconut");
    SuffixTree *tree2 = new SuffixTree("BAABAIAIIBI");
    // Print path
    tree1->visualize();
    tree2->visualize();
    return 0;
}

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


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







© 2021, kalkicode.com, All rights reserved