How find suffix in tree

344 views Asked by At

i am trying to make basic object oriented suffix tree console program and i dont know how to make boolean suffix(String s) method. My actual suffix method doesn't work properly. Finally it should looks like :

suffix tree with # as leafs

Node is for object, SuffixTree create tree and have methods for that tree, TestTree have main method for testing

Node

package trie3;

import java.util.HashMap;
import java.util.Map;

class Node{

   private final char currentValue;
   Map<Character,Node> children;
   Node(){
     this.currentValue = '#';
     this.children = new HashMap<Character,Node>();
   }    
   Node(char currentValue){ 
     this.currentValue = currentValue;
     this.children = new HashMap<Character,Node>();
   }       
   char getValue(){
     return this.currentValue;
   }
   void addChild(Node c){
    this.children.put(c.getValue(),c);
   }
   boolean hasChild(Node c){
    return this.children.containsKey(c.getValue());
   }  
   Node getChild(Node c){
     return this.children.get(c.getValue());
   }
  public String toString(){
    char currentValue = this.getValue();
    StringBuffer keys = new StringBuffer();
    for(char key:this.children.keySet()){
      keys.append("Current key:"+key+"\n");
    }
     return "Current value:"+currentValue+"\n"+
        "Keys:"+keys.toString(); 
   }
  }

SuffixTree

package trie3;

import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import trie3.Node;
public class SuffixTree{
  private Node root;

  private void log(Object l){
     System.out.println(l);
  }
  /*
   * Helper method that initializes the suffix tree
   */
  private Node createSuffixTree(String source,Node root){
    for(int i=1;i<source.length();i++){
      Node parent = new Node(source.charAt(i));
      if(root.hasChild(parent)){
        parent = root.getChild(parent);
      }
      Node current = parent;            
      for(int j=i+1;j<source.length();j++){
        Node temp = new Node(source.charAt(j));
    if(current.hasChild(temp)){
      temp = current.getChild(temp);
    }else{
      current.addChild(temp);
    }
        current = temp; 
      }
      root.addChild(parent);    
    }
    return root;         
  }

  /*
   Creates the suffix tree from the given string
   */
  public SuffixTree(String source){
    this.root = createSuffixTree(source,new Node()); // jj to je vychozi s # jj jo
  }   

  void printMap(Map<Character,Node> map){ // vytiskne vsechny znaky potomku daneho suffixu takze hahaa -- pokud budes od n tak to bude a h a a # tusim teda
     for(char c:map.keySet()){ 
      System.out.println("Current node has child: " +c);
    }
  }  

  boolean infix(String target){ // infix method
    Map<Character,Node> rootChildren = this.root.children;
   for(char c:target.toCharArray()){
      if(rootChildren.containsKey(c)){
        rootChildren = rootChildren.get(c).children;
      }else{
        return false;
      }
    }
    return true;
  }

    boolean suffix(String target){ // like infix but last char must be leaf
    Map<Character,Node> rootChildren = this.root.children;

   for(int i=0;i<target.length()-1;i++){
       printMap(rootChildren);
       char c = target.charAt(i);
      if(rootChildren.containsKey(c)){
        rootChildren = rootChildren.get(c).children;
      }else if(rootChildren == null){
          System.out.println("hash");
        return true;

      }else{
      return false;
      }
    }
return false;
  }

testTree

public class testTree {
       public static void main(String[] args){
    SuffixTree sTree = new SuffixTree("hahaa"); 

    //test suffix
   if(sTree.infix("ha")){ 
       System.out.println(":)");
   }
   else{
       System.out.println(":(");
   }

      if(sTree.suffix("ha")){ // true only for a,ha,haa,ahaa
       System.out.println(":)");
   }
   else{
       System.out.println(":(");
   }
   //test substring

    //  sTree.printMap();
   }
}
0

There are 0 answers