Warning: session_start(): open(/var/lib/php/sessions/sess_lst45qdjgj1k4vl4hq4o644g9o, O_RDWR) failed: No space left on device (28) in /var/www/tb-usercake/models/config.php on line 51
Warning: session_start(): Failed to read session data: files (path: /var/lib/php/sessions) in /var/www/tb-usercake/models/config.php on line 51
// from https://gist.github.com/bicepjai/3355993#file-gistfile1-java-L147
/*
Ukkonen's algorithm for linear time construction of suffix trees.
*/
public static int stacktrack;
public char TERMINATORS_RANGE = '\ud800';
public static int count=0;
public static void dfsd(Node c){
if (c.isLeaf()){
//print("\nbasecase");
//count++;
return;
}
Node a;
print(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(a);
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;
}
};
sclass 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(){
new Node node;
nodes.add(currentNode, node);
currentNode++;
ret 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