{{ message }}

Instantly share code, notes, and snippets.

# bicepjai/gist:3355993

Created Aug 15, 2012
Implementation of Ukkonen's algorithm to build a prefix tree in O(n)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 import java.util.*; public class ss { public static int stacktrack; public char TERMINATORS_RANGE = '\ud800'; public static int count=0; public static void dfsd(Node c){ if (c.isLeaf()){ //System.out.println("\nbasecase"); //count++; return; } Node a; System.out.println(c.sons.keySet()); Iterator it = c.sons.entrySet().iterator(); while (it.hasNext()) { Map.Entry pairs = (Map.Entry)it.next(); a = (Node)pairs.getValue(); for(int i=0;i>>>>>> ="+count+"= "+pairs.getKey() + " = " + a.edgeStart + " : " + a.edgeEnd ); stacktrack++; count++; dfsd(c.sons.get(pairs.getKey())); stacktrack--; for(int i=0;i sons; public Node(){ parent = suffixLink = null; edgeStart = edgeEnd = parentDepth = 0; sons = new TreeMap(); } // Returns true if there is a path starting at root having length position + 1 that ends // in the edge that reaches this node. public boolean inEdge(int position){ return parentDepth <= position && position < depth(); } public int edgeLength(){ return edgeEnd - edgeStart; } public int depth(){ return parentDepth + edgeLength(); } void link(Node son, int start, int end, String s){ // Links the current node with the son. The edge will have substring s[start, end) son.parent = this; son.parentDepth = this.depth(); son.edgeStart = start; son.edgeEnd = end; sons.put(s.charAt(start),son); } public boolean isLeaf(){ return sons.size() == 0; } }; class SuffixTree { ArrayList nodes; Node root, needSuffix; int currentNode; int length; char TERMINATORS_RANGE = '\ud800'; int termi=0; String generalized; public SuffixTree(String str) { nodes = new ArrayList(); currentNode = 0; str = str + (char)TERMINATORS_RANGE; length = str.length(); root = newNode(); build(root, str); } public SuffixTree(String[] stra) { nodes = new ArrayList(); currentNode = 0; root = newNode(); StringBuilder sb = new StringBuilder(); for (int i = 0; i < stra.length; i++) { sb.append(stra[i]); sb.append((char)(TERMINATORS_RANGE + i)); } generalized = sb.toString(); length = generalized.length(); build(root, generalized); } public SuffixTree() { nodes = new ArrayList(); currentNode = 0; root = newNode(); } void addString(String str){ str = str+ (char)(TERMINATORS_RANGE + termi); termi++; length = str.length(); build(root, str); } int nofnodes() { return currentNode; } Node newNode(){ nodes.add(currentNode,new Node()); currentNode++; return new Node(); } Node walkDown(Node c, int j, int i, String str) { int k = j + c.depth(); if (i - j + 1 > 0){ while (!c.inEdge(i - j)){ c = c.sons.get(str.charAt(k)); k += c.edgeLength(); } } return c; } void addSuffixLink(Node current){ if (needSuffix != null){ needSuffix.suffixLink = current; } needSuffix = null; } void build(Node root, String s) { Node c = newNode(); needSuffix = null; root.link(c, 0, length, s); // Indicates if at the beginning of the phase we need to follow the suffix link of the current node //and then walk down the tree using the skip and count trick. boolean needWalk = true; for (int i=0, j=1; i

### bicepjai commented Aug 15, 2012

This is taken from and converted to java from
https://gist.github.com/1268157

### olimpias commented Jun 6, 2018

Hi @bicepjai. There is a reference problem at NewNode() method. Could you update it like below? Thanks for this gist btw. You saved my day. :)
` Node newNode(){ Node node = new Node(); nodes.add(currentNode,node); currentNode++; return node; }`