0

我正在尝试制作基本的面向对象的后缀树控制台程序，但我不知道如何制作布尔后缀（String s）方法。我的实际后缀方法无法正常工作。最后它应该看起来像：

以 # 作为叶子的后缀树

节点用于对象，SuffixTree 创建树并具有该树的方法，TestTree 具有用于测试的主要方法

节点

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(); 
   }
  }

后缀树

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;
  }

测试树

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();
   }
}
4

0 回答 0